Zxy's Blog

二分查找插入点 二分查找不仅可用于搜索目标元素，还可用于解决许多变种问题，比如搜索目标元素的插入位置。 无重复元素的情况 给定一个长度为 nnn 的有序数组 nums 和一个元素 target ，数组不存在重复元素。现将 target 插入数组 nums 中，并保持其有序性。若数组中已存在元素 target ，则插入到其左方。请返回插入后 target 在数组中的索引。示例如下图所示。 如果想复用上一节的二分查找代码，则需要回答以下两个问题。 问题一：当数组中包含 target 时，插入点的索引是否是该元素的索引？ 题目要求将 target 插入到相等元素的左边，这意味着新插入的 target 替换了原来 target 的位置。也就是说，当数组包含 target 时，插入点的索引就是该 target 的索引。 问题二：当数组中不存在 target 时，插入点是哪个元素的索引？ 进一步思考二分查找过程：当 nums[m] < target 时 iii 移动，这意味着指针 iii 在向大于等于 target 的元素靠近。同理，指针 jjj 始终在向小于等于 target...

二分查找 二分查找（binary search）是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。 给定一个长度为 nnn 的数组 nums ，元素按从小到大的顺序排列且不重复。请查找并返回元素 target 在该数组中的索引。若数组不包含该元素，则返回 −1-1−1 。示例如下图所示。 如下图所示，我们先初始化指针 i=0i = 0i=0 和 j=n−1j = n - 1j=n−1 ，分别指向数组首元素和尾元素，代表搜索区间 [0,n−1][0, n - 1][0,n−1] 。请注意，中括号表示闭区间，其包含边界值本身。 接下来，循环执行以下两步。 计算中点索引 m=⌊(i+j)/2⌋m = \lfloor {(i + j) / 2} \rfloorm=⌊(i+j)/2⌋ ，其中 ⌊ ⌋\lfloor \: \rfloor⌊⌋ 表示向下取整操作。 判断 nums[m] 和 target 的大小关系，分为以下三种情况。 当 nums[m] < target 时，说明 target 在区间...

小结 重点回顾 图由顶点和边组成，可以表示为一组顶点和一组边构成的集合。 相较于线性关系（链表）和分治关系（树），网络关系（图）具有更高的自由度，因而更为复杂。 有向图的边具有方向性，连通图中的任意顶点均可达，有权图的每条边都包含权重变量。 邻接矩阵利用矩阵来表示图，每一行（列）代表一个顶点，矩阵元素代表边，用 111 或 000 表示两个顶点之间有边或无边。邻接矩阵在增删查改操作上效率很高，但空间占用较多。 邻接表使用多个链表来表示图，第 iii 个链表对应顶点 iii...

图的遍历 树代表的是“一对多”的关系，而图则具有更高的自由度，可以表示任意的“多对多”关系。因此，我们可以把树看作图的一种特例。显然，树的遍历操作也是图的遍历操作的一种特例。 图和树都需要应用搜索算法来实现遍历操作。图的遍历方式也可分为两种：广度优先遍历和深度优先遍历。 广度优先遍历 广度优先遍历是一种由近及远的遍历方式，从某个节点出发，始终优先访问距离最近的顶点，并一层层向外扩张。如下图所示，从左上角顶点出发，首先遍历该顶点的所有邻接顶点，然后遍历下一个顶点的所有邻接顶点，以此类推，直至所有顶点访问完毕。 算法实现 BFS 通常借助队列来实现，代码如下所示。队列具有“先入先出”的性质，这与 BFS 的“由近及远”的思想异曲同工。 将遍历起始顶点 startVet 加入队列，并开启循环。 在循环的每轮迭代中，弹出队首顶点并记录访问，然后将该顶点的所有邻接顶点加入到队列尾部。 循环步骤 2. ，直到所有顶点被访问完毕后结束。 为了防止重复遍历顶点，我们需要借助一个哈希集合 visited 来记录哪些节点已被访问。 哈希集合可以看作一个只存储 `key` 而不存储...

图的基础操作 图的基础操作可分为对“边”的操作和对“顶点”的操作。在“邻接矩阵”和“邻接表”两种表示方法下，实现方式有所不同。 基于邻接矩阵的实现 给定一个顶点数量为 nnn 的无向图，则各种操作的实现方式如下图所示。 添加或删除边：直接在邻接矩阵中修改指定的边即可，使用 O(1)O(1)O(1) 时间。而由于是无向图，因此需要同时更新两个方向的边。 添加顶点：在邻接矩阵的尾部添加一行一列，并全部填 000 即可，使用 O(n)O(n)O(n) 时间。 删除顶点：在邻接矩阵中删除一行一列。当删除首行首列时达到最差情况，需要将 (n−1)2(n-1)^2(n−1)2 个元素“向左上移动”，从而使用 O(n2)O(n^2)O(n2) 时间。 初始化：传入 nnn 个顶点，初始化长度为 nnn 的顶点列表 vertices ，使用 O(n)O(n)O(n) 时间；初始化 n×nn \times nn×n 大小的邻接矩阵 adjMat ，使用 O(n2)O(n^2)O(n2)...

图 图（graph）是一种非线性数据结构，由顶点（vertex）和边（edge）组成。我们可以将图 GGG 抽象地表示为一组顶点 VVV 和一组边 EEE 的集合。以下示例展示了一个包含 5 个顶点和 7 条边的图。 V={1,2,3,4,5}E={(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(4,5)}G={V,E}\begin{aligned} V & = \{ 1, 2, 3, 4, 5 \} \newline E & = \{ (1,2), (1,3), (1,5), (2,3), (2,4), (2,5), (4,5) \} \newline G & = \{ V, E \}...

小结 重点回顾 堆是一棵完全二叉树，根据成立条件可分为大顶堆和小顶堆。大（小）顶堆的堆顶元素是最大（小）的。 优先队列的定义是具有出队优先级的队列，通常使用堆来实现。 堆的常用操作及其对应的时间复杂度包括：元素入堆 O(log⁡n)O(\log n)O(logn)、堆顶元素出堆 O(log⁡n)O(\log n)O(logn) 和访问堆顶元素 O(1)O(1)O(1) 等。 完全二叉树非常适合用数组表示，因此我们通常使用数组来存储堆。 堆化操作用于维护堆的性质，在入堆和出堆操作中都会用到。 输入 nnn 个元素并建堆的时间复杂度可以优化至 O(n)O(n)O(n) ，非常高效。 Top-k 是一个经典算法问题，可以使用堆数据结构高效解决，时间复杂度为 O(nlog⁡k)O(n \log k)O(nlogk) 。 Q &...

Top-k 问题 给定一个长度为 $n$ 的无序数组 `nums` ，请返回数组中最大的 $k$ 个元素。 对于该问题，我们先介绍两种思路比较直接的解法，再介绍效率更高的堆解法。 方法一：遍历选择 我们可以进行下图所示的 kkk 轮遍历，分别在每轮中提取第 111、222、…\dots…、kkk 大的元素，时间复杂度为 O(nk)O(nk)O(nk) 。 此方法只适用于 k≪nk \ll nk≪n 的情况，因为当 kkk 与 nnn 比较接近时，其时间复杂度趋向于 O(n2)O(n^2)O(n2) ，非常耗时。 tip 当 $k = n$ 时，我们可以得到完整的有序序列，此时等价于“选择排序”算法。 方法二：排序 如下图所示，我们可以先对数组 nums 进行排序，再返回最右边的 kkk 个元素，时间复杂度为 O(nlog⁡n)O(n \log n)O(nlogn) 。 显然，该方法“超额”完成任务了，因为我们只需找出最大的 kkk 个元素即可，而不需要排序其他元素。 方法三：堆 我们可以基于堆更加高效地解决 Top-k...

建堆操作 在某些情况下，我们希望使用一个列表的所有元素来构建一个堆，这个过程被称为“建堆操作”。 借助入堆操作实现 我们首先创建一个空堆，然后遍历列表，依次对每个元素执行“入堆操作”，即先将元素添加至堆的尾部，再对该元素执行“从底至顶”堆化。 每当一个元素入堆，堆的长度就加一。由于节点是从顶到底依次被添加进二叉树的，因此堆是“自上而下”构建的。 设元素数量为 nnn ，每个元素的入堆操作使用 O(log⁡n)O(\log{n})O(logn) 时间，因此该建堆方法的时间复杂度为 O(nlog⁡n)O(n \log n)O(nlogn)...

堆 堆（heap）是一种满足特定条件的完全二叉树，主要可分为两种类型，如下图所示。 小顶堆（min heap）：任意节点的值 ≤\leq≤ 其子节点的值。 大顶堆（max heap）：任意节点的值 ≥\geq≥ 其子节点的值。 堆作为完全二叉树的一个特例，具有以下特性。 最底层节点靠左填充，其他层的节点都被填满。 我们将二叉树的根节点称为“堆顶”，将底层最靠右的节点称为“堆底”。 对于大顶堆（小顶堆），堆顶元素（根节点）的值是最大（最小）的。 堆的常用操作 需要指出的是，许多编程语言提供的是优先队列（priority queue），这是一种抽象的数据结构，定义为具有优先级排序的队列。 实际上，堆通常用于实现优先队列，大顶堆相当于元素按从大到小的顺序出队的优先队列。从使用角度来看，我们可以将“优先队列”和“堆”看作等价的数据结构。因此，本书对两者不做特别区分，统一称作“堆”。 堆的常用操作见下表，方法名需要根据编程语言来确定。 表   堆的操作效率 方法名 描述 时间复杂度 push() 元素入堆 O(log⁡n)O(\log...