力扣刷题笔记 #04 二分&分治

本文包含「二分&分治」类型题中的：二分查找、快速排序、归并排序、分块、倍增等。持续更新中。

题目描述：

方法1：

方法2：

方法3：

坑点：

二分查找

二分查找及其衍生题目通常会在一个「广义有序」背景下，很难直接使用 lower_bound() 解决，需要根据题意手写二分查找。通常要求时间复杂度 \(O(\log n )\) 或 \(O(n\log n)\)，数据量在 \(1e5\) 以上。

这里给出有序数组的二分查找模板：

int binarySearch(vector<int>& nums, int target) {
	int l = 0, r = nums.size() - 1, mid;
    while(l <= r){
        mid = (l + r) >> 1; // 位运算优先级最低，该方法不防溢出
        if(nums[mid] == target) return mid;
        else if(nums[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

如果需要找出大于、大于等于目标的第一个数的下标（手写 lower_bound 和 upper_bound），模板如下：

int boundSearch(vector<int>& nums, int target, bool lower){
    int l = 0, r = nums.size() - 1, mid, res = nums.size();
    while (l <= r) {
        imid = (l + r) >> 1;
        if(nums[mid] > target || (lower && nums[mid] >= target)){
            r = mid - 1;
            res = mid;
        }else
            l = mid + 1;
    }
    return res;
}

153. 寻找旋转排序数组中的最小值 (M)

题目描述：将一个升序数组旋转若干个单位（轮转平移），距离未知，找出数组中最小值的下标。

方法1：二分查找变种，按照如下规则二分，最终返回 \(nums[mid]\)，时间复杂度 \(O(\log n )\)。

• 如果 \(mid\) 大于等于两端，说明左侧升序，最小值在右侧，\(l=mid+1\)；
• 如果 \(mid\) 小于等于两端，说明右侧升序，最小值在左侧，也可能就是 \(mid\)，\(r=mid\)；
• 如果 \(mid\) 介于两者之间，说明此时已按顺序排列，\(r=mid - 1\)，也可以直接返回 \(nums[l]\)。

方法2：简化方法 1，观察发现后两种情况可以合并为「\(mid\) 小于右端」，此时令 \(r=mid\) 就行，最终返回 \(nums[l]\)。

33. 搜索旋转排序数组 (M)

题目描述：将一个升序数组旋转若干个单位（轮转平移），距离未知，设计算法查找一个给定值 target。

方法1：二分找到旋转排序数组中的最小值，即可将其分为两个升序数组，根据 \(nums[0]\) 与 \(target\) 大小判断目标在左段还是右段，再进行二分查找即可。时间复杂度 \(O(\log n )\)。

方法2：一次二分查找即可，按照如下规则二分，时间复杂度 \(O(\log n )\)。

• 如果 \(mid\) 就是 \(target\)，直接返回下标
• 如果 \(mid\) 大于等于左端（这里取等是因为 \(mid=l\) 时必须往右），说明左侧升序，此时比较 \(target\) 的大小：
  • 如果 \(target\in [nums[l],nums[mid])\)，说明目标位于左侧，则 \(r=mid-1\)
  • 否则说明位于右侧，则 \(l=mid+1\)
• 如果 \(mid\) 小于左端，说明右侧升序，此时比较 \(target\) 的大小：
  • 如果 \(target\in (nums[mid], nums[r]]\)，说明目标位于右侧，则 \(l=mid+1\)
  • 否则说明位于左侧，则 \(r=mid-1\)

34. 在排序数组中查找元素的第一个和最后一个位置 (M)

题目描述：给定一个升序数组和一个目标值，找出目标值的开始和结束位置，如果不存在则返回 [-1, -1]。

方法1：二分查找，在用 lower_bound 和 upper_bound 分别找出两个下标，判断下标指向的元素是否为末尾（防止越界）、是否为目标，如果是目标则返回 [l, r - 1]。时间复杂度 \(O(\log n)\)。

方法2：二分查找，在用 lower_bound 和 upper_bound 找出位置后，如果 l==r，则说明目标不存在。

方法3：封装，用 equal_range 封装上述两个函数，直接返回 \((l,r)\)。

74. 搜索二维矩阵 (M)

题目描述：给定一个矩阵，每行的元素从左到右升序排列、每行的第一个整数大于上一行的最后一个整数，判断目标值是否存在。

方法1：Z 字线性查找，从左上角开始向下搜索，直到遇到第一个大于目标值的数，开始向右搜素。复杂度 \(O(m+n)\)。

方法2：两次二分查找，先对第一列进行 upper_bound 找到第一个大于目标值的数（注意自定义比较函数），再在其上一行进行 binary_search 判断目标值是否存在。复杂度 \(O(\log m +\log n)=O(\log mn)\)。

方法3：一次二分查找，手写 \([0, mn-1]\) 的二分查找，将一维索引映射到二维矩阵，x=mat[mid/n][mid%n]。

240. 搜索二维矩阵 II (M)

题目描述：给定一个矩阵，每行的元素从左到右升序排列、每列的元素从上到下升序排列，从中找出目标值。

方法1：本题不能使用两次二分查找，因为不能确保目标值就出现在指定行，因此考虑对每行都进行二分，时间复杂度 \(O(n \log m)\)。

方法2：Z 字线性查找，从矩阵的右上角 \((0,n-1)\) 开始，每次将当前位置与目标进行比较，可以排除掉一行或一列，从而向左、向下走。如果超出了矩阵的边界，则说明目标值不存在，时间复杂度 \(O(n+m)\)。

假设当前位置为 \((x,y)\)，则目标是搜素以 \((x,y)\) 为右上角的矩形，其他位置已经排除：

• 如果 \(matrix[x][y]=target\)，说明搜素完成；
• 如果 \(matrix[x][y]>target\)，则当前元素及其下方的所有元素（第 \(y\) 列）都可以排除，向左走；
• 如果 \(matrix[x][y]<target\)，则当前元素及其左侧的所有元素（第 \(x\) 行）都可以排除，向下走。

方法3：抽象 BST，将右上角看作根节点，向左和向下的指针看作左、右子树，则可以将矩阵抽象为二叉搜索树。因此，如果当前节点大于目标，则应搜索左子树，即向左走；反之同理。本质与方法 2 相同。

二分答案

二分答案是二分查找里面较难的题型。当直接求一个最值很难，但我们可以很容易地在解空间做判定性问题，比如：能不能、偏大还是偏小，返回一个布尔值，从而缩小解空间。

这类题要求答案具有「单调性」且「范围已知」，最常见的类型是「最小值最大/最大值最小」题，随着答案的增大，解空间逐渐呈「能到不能」，具有单调性。

其他的类型比较隐蔽，但都有一个特点，要求一个最大/小值，且「小于该值的都 True、大于该值的都 False」具有明显的单调性，这类题往往伴随着贪心选择性。

整数域上的二分模板如下：

int l = 0, r = 1e9 + 3, mid;
auto check = [&](int x) {
    // 根据实际情况填写
    return bool;
};
// 最小化最大模板
while(l <= r){
    mid = (l + r) >> 1;
    if(check(mid))
        l = mid + 1; // 如果是最大值最小，则交换这两行
   	else
        r = mid - 1; // 如果是最大值最小，则交换这两行
}
return r;

2517. 礼盒的最大甜蜜度 (M)

题目描述：给定一个整数数组，每个元素代表一类糖果的价格，要求从中选出 k 类糖果打包成礼盒，定义甜蜜度为礼盒中任选两类糖果价格差的最小值，求可能的最大甜蜜度。

方法1：暴力枚举，当所选糖果价格越离散，甜蜜度越大。先排序再逐个枚举，难以实现，复杂度过高。

方法2：二分答案 + 贪心，由于随着甜蜜度的增大，可行选法变少，有单调性且答案取 \([0, \frac{Pmax-Pmin}{k}]\)。先将价格排序，每次 check(x) 时贪心选择间距大于 \(x\) 的糖果，如果能选完，则可行。时间复杂度 \(O(n\log n)\)。

2560. 打家劫舍 IV (M)

题目描述：给定一个非负整数数组 nums 表示每个房子的钱，小偷不会窃取相邻的房屋，窃取能力定义为整个窃取过程中能从单间房屋窃取的最大金额。另给一个整数 k 表示至少窃取的房间数，求最小窃取能力。

方法1：二分答案 + DP，由于随着窃取能力的增加，能窃取的房间数单调不减，且答案取 \([0,MaxNum]\)。二分窃取能力，每次 check(x) 时用一维线性 DP，\(dp[i]\) 表示到下标 \(i\) 能偷窃的最大值，如果 \(dp[n] \geqslant k\) 则可行，时间复杂度 \(O(n\log n)\)。

方法2：二分答案 + 贪心，每次 check(x) 时贪心窃取尽量密集的房子，\(cnt \geqslant k\) 则可行。时间复杂度 \(O(n\log n)\)。

287. 寻找重复数 (M)

题目描述：给定一个包含 \(n + 1\) 个整数的数组，其数字都在 \([1, n]\) 范围内，假设数组中有且仅有一个重复的整数，找出数组中重复的数字，要求空间复杂度 \(O(1)\)。

方法1：二分答案，定义 \(cnt[i]\) 表示数组中小于等于 \(i\) 的数的个数，假设重复数是 \(x\)，则 \([1,x-1]\) 里所有数都满足 \(cnt[i] \leq i\)；而 \([x,n]\) 里的所有数满足 \(cnt[i]>i\)。因此可以二分枚举 \(x\) 直到找到。时间复杂度 \(O(n\log n)\)。

方法2：二进制，预处理 \([1,n]\) 这 \(n\) 个数「每一位为 \(1\) 的个数之和」，如果当前数组的「每一位为 \(1\) 的个数之和」大于期望值，则说明重复数的这一位为 \(1\)。遍历每一位即可，时间复杂度 \(O(n \log n)\)。

方法3：抽象成环形链表寻找入口，快慢指针，先用 \(fast\) 和 \(slow\) 相遇，再用 \(pos\) 和 \(slow\) 相遇，时间复杂度 \(O(n)\)。

2576. 求出最多标记下标 (M)

题目描述：给定一个整数数组，一开始所有下标都没有标记。选择两个未标记的下标，满足 2*nums[i]<=nums[j]，标记 i 和 j。执行上述操作任意次，求最多可以标记的下标数。

下标与顺序无关，因此先对数组排序处理，排序后配对的数应当分布于两侧。

方法1：二分答案，假设答案为 \(x\) 对，则小于 \(x\) 对肯定可以，大于 \(x\) 对肯定不行，具有单调性。二分枚举 \(x\)，每次 check(x) 时只需判断最左和最右 \(x\) 个数是否一一配对即可。时间复杂度 \(O(n\log n)\)。

方法2：贪心 + 双指针，由于配对的数分布于两侧，最多可有 \(n/2\) 组配对，且左边匹配成功的数必定是最小的 \(x\) 个数。因此顺序枚举左边 \(i\)，并从右边找到第一个满足条件的 \(j\)，一直到右边数遍历完。排序时间复杂度 \(O(n\log n)\)。

分治

53. 最大子数组和 (M)

题目描述：给定包含正负整数的数组，找出具有最大和的连续子数组（子数组最少包含一个元素），返回最大和。

方法1：滑动窗口 + 贪心，累计窗口内的总和，当和为负数时，说明窗口内的数字不会对后来的数字有贡献，可以将左指针快速前移到右指针所在处，并清空窗口总和，重新累计。时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

方法2：DP，用 \(dp[i]\) 表示以第 \(i\) 个数结尾的「连续子数组的最大和」，对于每个数考虑单独成段还是加入 \(dp[i-1]\) 对应的段，时空复杂度均为 \(O(n)\)。 \[ dp\left[ i \right] =\max \left\{ dp\left[ i-1 \right] +nums\left[ i \right] , nums\left[ i \right] \right\} \] 方法3：DP + 空间优化，每个状态只由前一个状态转移过来，空间复杂度 \(O(1)\)。

方法4：分治 + 暴力扫描，将数组从中间割开，则最大子段可能在左边、右边、过中点的两边，对于第三种可能，从中点开始扫到两边，得到的两个最大值相加即可。递归 \(O(\log n)\) 层，每层扫一遍，时间复杂度 \(O(n\log n)\)。

方法5：分治 + 线段树思想。第三种可能可以继续递归计算，递归 \(O(\log n)\) 层，每层 \(2^{i-1}\) 个节点，时间复杂度 \(O(n)\)。

首先定义一个操作 get(a, l, r) 表示查询序列 \(a\) 中 \([l,r]\) 区间的最大子段和，对于长度大于 \(1\) 的区间，取 \(m=(l+r)/2\)，分治求解 \([l,m]\) 和 \([m+1,r]\)。这是基础的分治操作，方法 4、5 都一样。

但是如果想优化扫描过程，每次递归需要维护的状态量有哪些呢？首先肯定要有 \(mSum\) 表示区间内的最大子段和，当最大子段跨越 \(m\) 时，还需要「左子区间包含右端点的最大子段和」与「右子区间包含左端点的最大子段和」，因此还要维护 \(lSum\) 和 \(rSum\) 表示包含 \(l\) 和包含 \(r\) 的最大子段和。

对于 \([l,r]\) 的 \(lSum\)，要么等于「左子区间的 \(lSum\)」，要么等于「左子区间的总和 + 右子区间的 \(lSum\)」，\(rSum\) 同理。因此还要维护每个区间的总和 \(iSum\)，等于「左子区间的 \(iSum\) + 右子区间的 \(iSum\)」。

这其实是线段树 PushUp 的思想，如果将每个节点的信息用建树存储，则可以在 \(O(\log n)\) 时间内求到任意 \([l,r]\) 区间的答案，适用于多次查询。

Todo 918. 环形子数组和 (M)

快速排序

时间复杂度 \(O(n\log n)\)，递归需要考虑栈空间，空间复杂度 \(O(\log n)\)，模板如下：

// 极简快排，待排序数组 a[N] 为全局变量
void qs(int l, int r){
	int i=l, j=r, x=a[(l+r)>>1];
	while(i<=j){
		while(a[i]<x) ++i;
		while(a[j]>x) --j;
		if(i<=j) swap(a[i++],a[j--]);
	}
	if(l<j) qs(l,j);
	if(i<r) qs(i,r);
}

// partition 函数式写法，方便修改，但会被全相同数字样例卡
void QuickSort(vector<int>& nums, int low, int high){
    if(low < high) {
        int pivotpos = RandomizedPartition(nums, low, high);
        QuickSort(nums, low, pivotpos - 1);
        QuickSort(nums, pivotpos + 1, high);
    }
}
// 随机选枢轴，防止被接近有序的样例卡
int RandomizedPartition(vector<int>& nums, int low, int high) {
    int pos = rand() % (high - low + 1) + low;
    swap(nums[low], nums[pos]);
    return Partition(nums, low, high);
}
int Partition(vector<int>& nums, int low, int high){
    int pivot = nums[low];
    while(low < high) {
        while(low < high && nums[high] >= pivot) --high;
        nums[low] = nums[high];
        while(low < high && nums[low] <= pivot) ++low;
        nums[high] = nums[low];
    }
    nums[low] = pivot;
    return low;
}

快排的优化思路有很多：

1. 枢轴选取：Median3、随机抽取（尽可能使分割均匀，防止退化到 \(O(n^2)\)；
2. 扫描顺序：从两侧以双指针的形式靠拢，可以加大均匀分割的概率；
3. 优化剪枝：当长度 \(n<16\) 时使用非递归排序、或当递归深度达到指定值时采用非递归排序；
4. 尾递归：在处理两个子问题时，可以先处理更小规模的问题，减小递归深度，节约栈开销；
5. 三向切分：划分出小于 pivot、等于 pivot、大于 pivot 三个分区，来避免大量相同元素时退化。

215. 数组中的第K个最大元素 (M)

题目描述：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

方法1：直接排序，快排时间复杂度 \(O(n\log n)\)，空间复杂度 \(O(\log n)\)。

方法2：快速选择 Kth，每次 Partition 都将数组分为两部分，并确定一个元素的最终位置。通过判断两侧元素的个数就可以知道第 k 大元素位于哪一侧，再递归一侧即可。时间复杂度 \(O(n)\)，空间复杂度 \(O(\log n)\)。

修改 QuickSort() 主函数，传入参数 k，先进行 Partition 操作，无需随机。

Partition 后记枢轴右边的元素个数为 x，如果 x==k-1，直接返回枢轴；如果 x>k-1 则递归右边，传入参数 k；否则递归左边，传入参数 k-x-1。

也可以直接使用 C++ 的 nth_element() 函数，可以将第 k 大的元素放至对应位置，并确保左侧小、右侧大。

方法3：堆排序，维护一个大小为 \(k\) 的小顶堆，每遍历到一个元素，如果小于堆顶元素则不考虑；否则将堆顶元素弹出，放入新数下滤。最后堆顶元素就是目标值，时间复杂度为 \(O(n\log k)\)，空间复杂度 \(O(k)\)。

坑点：很多人以为找第 K 大元素就要用大顶堆，实则不然。第 K 大元素在前 K 大元素中就是最小元素，因此要用小顶堆维护。

347. 前 K 个高频元素 (M)

题目描述：给定整数数组 nums 和整数 k，请返回数组中出现频率前 k 高的元素，顺序任意。

方法1：哈希表 + 快速选择 Kth，哈希表预处理得到频率数组。由于题目要求列出前 K 个元素，因此不建议自己实现二分，直接 nth_element() 解决，时间复杂度 \(O(n)\)，空间复杂度 \(O(\log n)\)。

方法2：哈希表 + 优先队列，哈希表预处理得到频率数组。优先队列，维护一个大小为 \(k\) 的小顶堆，时间复杂度为 \(O(n\log k)\)，空间复杂度 \(O(k)\)。

1619. 删除某些元素后的数组均值 (E)

题目描述：给定一个整数数组 arr，删除最小的 5% 个数和最大的 5% 个数后，返回剩余数的平均值。

方法1：优先队列，用最大堆和最小堆分别找出两部分，但在数据量小的情况下复杂度常数略大。

方法2：排序，使用 STL 里的 sort 和 accumulate，复杂度 \(O(n \log n)\) 但是比上一个方法优化更快。

方法3：快速选择，当成 TopK 问题，使用 STL 里的 nth_element，将第 K 小的元素、第 K 大的元素找出，并且两边分别是更小和更大的数，只需将中间部分求和即可。时间复杂度 \(O(n)\)。

4. 寻找两个正序数组的中位数 (H)

题目描述：给定两个长为 m 和 n 的有序数组，要求找到两个有序数组合并后数组的中位数。（也可以说是第 \(k\) 大的数）

方法1：直接归并，时间复杂度为 \(O(m+n)\)。

方法2：二分 + 递归，类似 Kth 问题，但是省去 Partition 的过程（数组本身有序），时间复杂度为 \(O\left(\log (m+n)\right)\)。

看成 Kth 问题，当 \(m+n\) 为奇数时，\(k=(m+n)/2+1\)；为偶数时，\(k=(m+n)/2\) 和 \((m+n)/2+1\)。每次从两个数组中取第 \(k/2\) 个数进行比较，将小的那一方的前 \(k/2\) 个数全部排除。

证明：\(A[k/2]\) 和 \(B[k/2]\) 要想成为第 \(k\) 小的数，那必须要比 \(k-1\) 个数大才行。如果 \(A[k/2]＜B[k/2]\)，则 \(A[k/2]\) 至多只能比 \(k-2\) 个数大，因此 \(A\) 数组可以全部丢弃，但是 \(B\) 数组则都有可能。

递归的结束条件为：如果一个数组已经被丢弃为空，则可以直接返回另一个数组的第 \(k\) 小数；否则如果 \(k=1\)，此时只要返回两个数组首元素的最小值即可。

方法3：划分数组，中位线两边的数目相等，且左边最大值小于右边最小值。时间复杂度为 \(O\left(\log \min (m,n)\right)\)。

坑点：方法 2 中，如果取第 \(k/2\) 个数时数组越界（没那么多数可选），则需要选取对应数组中的最后一个元素，此时循环过后不能直接将 \(k\) 减去 \(k/2\)。

归并排序

时间复杂度 \(O(n\log n)\)，递归写法，且用到辅助数组，空间复杂度 \(O(n)\)，模板如下：

int t[maxn];
void ms(int l, int r){
	if(l>=r) return;
	int mid=(l+r)>>1, p=l, q=mid+1, ct=l;
	ms(l,mid);
	ms(mid+1,r);
	while(p<=mid || q<=r){
		if((p>mid) || (q<=r && a[q]<a[p])) t[ct++]=a[q++];
		else t[ct++]=a[p++];
	}
	for(int i=l; i<=r; i++) a[i]=t[i];
}

Todo 逆序对

148. 排序链表 (M)

题目描述：给定链表的头结点 head，请将其按升序排列并返回排序后的链表 。

方法1：自顶向下归并排序，以链表中点为界将其拆分为两个子链表，对两个子链表递归排序后，合并两个有序链表，时间复杂度 \(O(n\log n)\)，空间复杂度为递归栈深度 \(O(\log n)\)。

方法2：自底向上归并排序，记每次要排序的长度为 \(len\)，初始 \(len=1\)，将子链表两两归并后，\(len\) 倍增。无需递归，空间复杂度 \(O(1)\)。

775. 全局倒置与局部倒置 (M)

题目描述：给定一个 \([0,n-1]\) 随机排列的数组，定义两个相邻元素的逆序对为局部倒置，任意两个元素的逆序对为全局倒置，判断该数组中两种倒置的数量是否相等。

方法1：暴力，全局倒置可以用归并获取，局部倒置可以冒泡扫描一遍获取，时间复杂度 \(O(n \log n)\)，空间复杂度 \(O(n)\)。

方法2：转换思维，只需判断是否存在「跨元素的逆序对」即可，如果一次冒泡扫描能让数组变得有序，则必然不存在跨元素的逆序对，时间复杂度 \(O(n)\)。

方法3：贪心，维护前缀最大值，如果 \(maxPre\) 大于 \(nums[i+2]\)，则存在跨元素的逆序对，时间复杂度 \(O(n)\)。

方法4：归纳，可以证明满足题意的充要条件是「每个元素 \(x\) 都要满足 \(\left| nums\left[ x \right] -x \right|\leqslant 1\)」，时间复杂度 \(O(n)\)。

对于 \([0,n-1]\) 的原始问题，如果满足题意，最小元素 \(0\) 必然在前两个位置：

• 若 \(nums[0]=0\)，则转换为 \([1,n-1]\) 的子问题；
• 若 \(nums[1]=0\)，则次小元素 \(1\) 必须在第一个位置，转为 \([2, n-1]\) 的子问题。

以此类推，元素 \(1\) 必须在下标为 \(0,1,2\) 的位置，元素 \(2\) 必须在下标为 \(1,2,3\) 的位置，每个数偏离目标位置不能超过一个单位。

分块

倍增

二分的逆过程是倍增，每次根据已经得到的信息，将考虑的范围增加一倍， 从而加速操作。

快速幂就是经典的倍增算法。

// 非递归快速幂，最常用
ll qpow(ll a, ll n) {
    ll ans = 1;
    while (n) {
        if (n & 1)     // 如果 n 的当前末位为 1
            ans *= a;  // ans 乘上当前的 a
        a *= a;        // a 倍增
        n >>= 1;       // n 往右移一位
    }
    return ans;
}

// 非递归快速幂，带 mod 运算，常用
ll qpowmod(ll a, ll n, ll mod) {
    ll ans = 1;
    while (n) {
        if (n & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return ans % mod;
}

Todo 50. 快速幂