【C++算法】分治（快排 归并）

1. 引言

1.1 分治算法思想

☘️☘️☘️规模为n的原问题的解无法直接求出，进行问题规模缩减，划分子问题（这里子问题相互独立而且和原问题解的性质是相同的，只是问题规模缩小了）。如果子问题的规模仍然不够小，再进行子问题划分，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止，最后求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。

1.2 分治算法适用条件

分治算法所能解决的问题一般具有以下几个特征：

• 原问题的规模缩小到一定的程度就可以很容易地解决
• 原问题可以分解为若干个规模较小的相同问题，即原问题具有最优子结构性质
• 利用原问题分解出的子问题的解可以合并为原问题的解
• 原问题分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题（这条特征涉及到分治法的效率，如果各个子问题不独立，也就是子问题划分有重合部分，则分治法要重复的求解1公共子问题的解，此时虽然也可用分治法，但采用动态规划更好）

经典例题如下：

2. 快排

2.1 颜色分类

题目描述：给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

思路：

三指针，用 i 来遍历数组，left 标记 0 区域的最右侧，right 标记 2 区域的最左侧

• [0，left]：全部都是 0 
• [left + 1，i - 1]：全都是 1
• [i，right - 1]：待扫描元素
• [right，n - 1]：全都是2

然后分类讨论，对于nums[ i ].

如果为 0，则 swap(nums[++left]，nums[ i++ ]) 这里 i++原因是因为交换后的数已经被扫描过了

如果为 1，则 i++.

如果为 2，则 swap(nums[--right]，nums[ i ])

注：由于下标从0开始，那么对于left应该初始化为-1

class Solution {
public:void sortColors(vector<int>& nums) {int n = nums.size();int l = -1, r = n, i = 0;while (i < r){if (nums[i] == 0)swap(nums[++l], nums[i++]);else if (nums[i] == 1) i++;else if (nums[i] == 2) swap(nums[--r], nums[i]);}}
};

2.2 排序数组

给你一个整数数组 nums，请你将该数组升序排列。

方法一：（数组分两块）

思路： 找个基准值，把一个大数组分成两个小数组

class Solution {
public:void QuickSort(vector<int>& q, int l, int r){if (l >= r) return;int x = q[l + r >> 1];int i = l - 1, j = r + 1;while (i < j){do i++; while (q[i] < x);do j--; while (q[j] > x);if (i < j)swap(q[i], q[j]);}QuickSort(q, l, j);QuickSort(q, j + 1, r);}vector<int> sortArray(vector<int>& nums) {auto q = nums;int n = nums.size();QuickSort(q, 0, n - 1);return q;}
};

方法二：数组分三块 + 随机选择基准元素

思路：数组分三块 + 随机选择基准元素

class Solution {
public:int getRandom(vector<int>& nums, int left, int right) {int k = rand();return nums[k % (right - left + 1) + left];}vector<int> sortArray(vector<int>& nums){srand(time(NULL));QuickSort(nums, 0, nums.size() - 1);return nums;}void QuickSort(vector<int>& nums, int l, int r){if (l >= r) return;int k = getRandom(nums, l, r);int i = l, left = l - 1, right = r + 1;while (i < right){if (nums[i] < k) swap(nums[++left], nums[i++]);else if (nums[i] == k) i++;else swap(nums[--right], nums[i]);}QuickSort(nums, l, left);QuickSort(nums, right, r);}
};

2.3 数组中的第K个最大元素

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

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

思路：数组分三块 + 选择基准元素

class Solution {
public:int sort(vector<int>& nums, int l,int r, int k){if (l == r) return nums[l];// 1. 找基准元素int key = nums[l + r >> 1];// 2. 根据基准元素把数组分三块int i = l, left = l - 1, right = r + 1;while (i < right){if (nums[i] < key) swap(nums[++left], nums[i++]]);else if (nums[i] == key) i++;else swap(nums[--right], nums[i]);}// 3. 分情况讨论int c = r - right + 1, b = right - left - 1;if (c >= k) return sort(nums, right, r, k);else if (b + c >= k) return key;else return sort(nums, l, left, k - b - c);}int findKthLargest(vector<int>& nums, int k) {return sort(nums, 0, nums.size() - 1,k);}
};

2.4 库存管理 III

题目描述：仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。

思路：

该题目本质就是求数组的最小 k 个元素

class Solution {
public:void sort(vector<int>& nums, int l, int r, int k) {if (l >= r) return;// 1. 基准元素 + 数组分块int key = nums[l + r >> 1];int left = l - 1, right = r + 1, i = l;while (i < right){if (nums[i] < key) swap(nums[++left], nums[i++]);else if (nums[i] == key) i++;else swap(nums[--right], nums[i]);}// 2. 分情况讨论int a = left - l + 1, b = right - left - 1;if (a > k) sort(nums, l, left, k);else if (a + b >= k) return;else sort(nums, right, r, k - a - b);}vector<int> inventoryManagement(vector<int>& stock, int cnt) {sort(stock, 0, stock.size() - 1, cnt);return { stock.begin(),stock.begin() + cnt };}
};

 3. 归并

 3.1 归并排序

class Solution {
public:int tmp[100005];void mergesort(vector<int>& nums, int l, int r){if (l >= r) return;// 1. 根据中间元素，划分区间int mid = l + r >> 1;// 2. 处理左右两部分mergesort(nums, l, mid), mergesort(nums, mid + 1, r);// 3. 处理一左一右情况int k = 0, i = l, j = mid + 1;while (i <= mid && j <= r){if (nums[i] <= nums[j]) tmp[k++] = nums[i++];else tmp[k++] = nums[j++];}// 4. 处理剩下排序过程while (i <= mid) tmp[k++] = nums[i++];while (j <= r) tmp[k++] = nums[j++];// 5. 更新原数组for (i = l, j = 0; i <= r; i++, j++) nums[i] = tmp[j];}vector<int> sortArray(vector<int>& nums) {int n = nums.size();mergesort(nums, 0, n - 1);return nums;}
};

3.2 交易逆序对的总数

题目描述：在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。

对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对。
重要的地方在于，一个元素可以不只是在一个逆序对中存在。如果 k > j > i 且 a[i] > a[j] > a[k]，那么这里
有两个含 a[i] 的逆序对，分别是 (a[i], a[j]) 和 (a[i], a[k]), a[i]是可以使用多次的。

那么第二步是分析问题，这里我们可以使用分治法解决问题。

我们将序列从中间分开，将逆序对分成三类：

• 两个元素都在左边；
• 两个元素都在右边；
• 两个元素一个在左一个在右；

因此这就是我们算法的大致框架：

计算逆序对的数量（序列）：
1. 递归算左边的；
2. 递归算右边的；
3. 算一个左一个右的；
4. 把他们加到到一起。

class Solution {
public:int tmp[100005];int mergesort(vector<int>& nums, int l, int r) {if (l >= r) return 0;int mid = l + r >> 1;int res = mergesort(nums, l, mid) + mergesort(nums, mid + 1, r);int k = 0, i = l, j = mid + 1;while (i <= mid && j <= r){if (nums[i] <= nums[j]) tmp[k++] = nums[i++];else {tmp[k++] = nums[j++];res += mid - i + 1; //区间内逆序数目}}while (i <= mid) tmp[k++] = nums[i++];while (j <= r) tmp[k++] = nums[j++];for (i = l, j = 0; i <= r; i++, j++) nums[i] = tmp[j];return res;}int reversePairs(vector<int>& record) {return mergesort(record, 0, record.size() - 1);}
};

3.3 计算右侧小于当前元素的个数

给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

思路：该题与上题算逆序对数目类似，需要用个数组来存 nums 的下标

当前元素后面，有多少个比我小。（降序）

class Solution {
public:int tmpNums[500005];int tmpIndex[500005];vector<int> ret;vector<int> index; //记录nums 当前元素的原始下标void mergesort(vector<int>& nums, int l, int r) {if (l >= r) return;// 1. 根据中间元素，划分区间int mid = l + r >> 1;// 2. 处理左右两部分mergesort(nums, l, mid), mergesort(nums, mid + 1, r);// 3. 处理一左一右情况int k = 0, i = l, j = mid + 1;while (i <= mid && j <= r){if (nums[i] <= nums[j]) {tmpIndex[k] = index[j];tmpNums[k++] = nums[j++];}else {ret[index[i]] += r - j + 1;tmpIndex[k] = index[i];tmpNums[k++] = nums[i++];}}// 4. 处理剩下排序过程while (i <= mid) {tmpIndex[k] = index[i];tmpNums[k++] = nums[i++];}while (j <= r) {tmpIndex[k] = index[j];tmpNums[k++] = nums[j++];}// 5. 更新原数组for (i = l, j = 0; i <= r; i++, j++) {index[i] = tmpIndex[j];nums[i] = tmpNums[j];}}vector<int> countSmaller(vector<int>& nums) {int n = nums.size();ret.resize(n);index.resize(n);// 初始化一下 index 数组for (int i = 0; i < n; i++) index[i] = i;mergesort(nums, 0, n - 1);return ret;}
};

3.4 翻转对

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

思路：

方法一（降序）： 找当前元素后面，有多少元素的两倍比我小，res += r - j + 1; 

方法二（升序）： 找当前元素之前，有多少元素的一半比我大 res += mid - i + 1;

 方法一：

class Solution {
public:int tmp[100005];int mergesort(vector<int>& nums, int l, int r){if (l >= r) return 0;// 1. 根据左右元素划分区间int mid = (r + l) >> 1;// 2. 计算左右两侧翻转对int res = mergesort(nums, l, mid) + mergesort(nums, mid + 1, r);// 3. 先计算翻转对数量int i = l, j = mid + 1;while (i <= mid) //降序的情况{if (j <= r && nums[j] >= nums[i] / 2.0) j++;if (j > r) break;res += r - j + 1;i++;}// 4. 合并有序数组i = l, j = mid + 1;int k = l;while (i <= mid && j <= r){if (nums[i] <= nums[j]) tmp[k++] = nums[j++];else tmp[k++] = nums[i++];}while (i <= mid) tmp[k++] = nums[i++];while (j <= r) tmp[k++] = nums[j++];for (j = l; j <= r; j++) nums[j] = tmp[j];return res;}int reversePairs(vector<int>& nums) {return mergesort(nums, 0, nums.size() - 1);}
};

方法二：

class Solution {
public:int tmp[100005];int mergesort(vector<int>& nums, int l, int r){if (l >= r) return 0;// 1. 根据左右元素划分区间int mid = (r + l) >> 1;// 2. 计算左右两侧翻转对int res = mergesort(nums, l, mid) + mergesort(nums, mid + 1, r);// 3. 先计算翻转对数量int i = l, j = mid + 1;while (j <= r) //升序的情况{while (i <= mid && nums[j] >= nums[i] / 2.0) i++;if (i > mid) break;res += mid - i + 1;j++;}// 4. 合并有序数组i = l, j = mid + 1;int k = 0;while (i <= mid && j <= r){if (nums[i] <= nums[j]) tmp[k++] = nums[i++];else tmp[k++] = nums[j++];}while (i <= mid) tmp[k++] = nums[i++];while (j <= r) tmp[k++] = nums[j++];for (i = l, j = 0; i <= r; i++, j++) nums[i] = tmp[j];return res;}int reversePairs(vector<int>& nums) {return mergesort(nums, 0, nums.size() - 1);}
};