算法专题(八)：分治-归并排序

目录

一、排序数组

1.1 题目

2.2 思路

2.3 代码实现

二、LCR 170. 交易逆序对的总数 （数组中的逆序对）

2.1 题目

2.2 思路

方法一：快速统计出某个数前面有多少个数比它大

方法二：快速统计出某个数后面有多少个数比它小

2.3 代码实现

​编辑 三、计算右侧小于当前元素的个数 

3.1 题目

3.2 思路

 3.3 代码实现

四、翻转对 

4.1 题目

4.2 思路

4.3 代码实现

---

算法专题：uyeonashi的博客-CSDN博客

一、排序数组

1.1 题目

2.2 思路

归并排序的流程充分的体现了「分而治之」的思想，大体过程分为两步：
◦ 分：将数组一分为二为两部分，一直分解到数组的长度为 1 ，使整个数组的排序过程被分为
「左半部分排序」 + 「右半部分排序」；
◦ 治：将两个较短的「有序数组合并成一个长的有序数组」，一直合并到最初的长度。

2.3 代码实现

class Solution {
public:vector<int> tmp; // 辅助数组void mergeSort(vector<int>& nums,int left,int right){if(left >= right) return;// 1. 选择中间点划分区域int mid = (left+right) >> 1;//[left,mid] [mid+1,right]// 2. 把左右区间排序mergeSort(nums,left,mid);mergeSort(nums,mid+1,right);//3. 合并两个有序数组int cur1 = left,cur2 = mid+1, i = 0;while(cur1 <= mid && cur2<=right)tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];//处理没有遍历完的数组while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];//将辅助数组中的值放到原数组中for(i = left; i<= right; i++)nums[i] = tmp[i-left];}vector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());mergeSort(nums,0,nums.size()-1);return nums;}
};

二、LCR 170. 交易逆序对的总数 （数组中的逆序对）

2.1 题目

2.2 思路

用归并排序求逆序数是很经典的方法，主要就是在归并排序的合并过程中统计出逆序对的数量，也就是在合并两个有序序列的过程中，能够快速求出逆序对的数量。
我们将这个问题分解成几个小问题，逐一破解这道题。

注意：默认都是升序，如果掌握升序的话，降序的归并过程也是可以解决问题的。
• 先解决第一个问题，为什么可以利用归并排序？
如果我们将数组从中间划分成两个部分，那么我们可以将逆序对产生的方式划分成三组：

• 逆序对中两个元素：全部从左数组中选择
• 逆序对中两个元素：全部从右数组中选择
• 逆序对中两个元素：一个选左数组另一个选右数组

根据排列组合的分类相加原理，三种种情况下产生的逆序对的总和，正好等于总的逆序对数量。

 而这个思路正好匹配归并排序的过程：

• 先排序左数组；
• 再排序右数组；
• 左数组和右数组合二为一

因此，我们可以利用归并排序的过程，先求出左半数组中逆序对的数量，再求出右半数组中逆序对的数量，最后求出一个选择左边，另一个选择右边情况下逆序对的数量，三者相加即可。

 • 解决第二个问题，为什么要这么做？
在归并排序合并的过程中，我们得到的是两个有序的数组。我们是可以利用数组的有序性，快速统计出逆序对的数量，而不是将所有情况都枚举出来。

 • 最核心的问题，如何在合并两个有序数组的过程中，统计出逆序对的数量？

合并两个有序序列时求逆序对的方法有两种：

• 快速统计出某个数前面有多少个数比它大；
• 快速统计出某个数后面有多少个数比它小；

方法一：快速统计出某个数前面有多少个数比它大

通过一个示例来演示方法一：
假定已经有两个已经有序的序列以及辅助数组 left = [5, 7, 9] right = [4, 5, 8] help = [ ]，通过合并两个有序数组的过程，来求得逆序对的数量：
规定如下定义来叙述过程:
        cur1 遍历 left 数组，cur2 遍历 right 数组
        ret 记录逆序对的数量

第一轮循环：
        left[cur1] > right[cur2]，由于两个数组都是升序的，那么我们可以断定，此刻 left 数组中[cur1, 2] 区间内的 3 个元素均可与 right[cur2] 的元素构成逆序对，因此可以累加逆序对的数量 ret+= 3，并且将 right[cur2] 加入到辅助数组中，cur2++ 遍历下一个元素。
第一轮循环结束后：left = [5, 7, 9] right = [x, 5, 8] help = [4] ret = 3 cur1 = 0 cur2 = 1

 第二轮循环：
        left[cur1] == right[cur2]，由于两个数组都是升序，这个时候对于元素 left[cur1] 来说，我们已经可以断定 right 数组中 [0, cur2) 左闭右开区间上的元素都是比它小的。因此此时可以统计逆序对的数量 ret += cur2 - 0，并且将 left[cur1] 放入到辅助数组中去，cur1++ 遍历下一个元素。
第二轮循环结束后：left = [x, 7, 9] right = [x, 5, 8] help = [4, 5] ret = 1 cur1 = 1 cur2 = 1

第三轮循环：
        left[cur1] > right[cur2]，与第一轮循环相同，此刻 left 数组中[cur1, 2] 区间内的 2 个元素均可与 right[cur2] 的元素构成逆序对，更新 ret 的值为 ret += 2，并且将 right[cur2] 加入到辅助数组中去，cur2++ 遍历下一个元素。
第三轮循环结束后：left = [x, 7, 9] right = [x, x, 8] help = [4, 5, 5] ret = 5 cur1 = 1 cur2 = 2

 第四轮循环：
        left[cur1] < right[cur2]，由于两个数组都是升序的，因此我们可以确定 left[cur1] 比 right 数组中的所有元素都要小。left[cur1] 这个元素是不可能与 right 数组中的元素构成逆序对。因此，大胆的将 left[cur1] 这个元素加入到辅助数组中去，不更细 ret 的值。
第四轮循环结束后：left = [x, x, 9] right = [x, x, 8] help = [4, 5, 5, 7] ret = 5 cur1 = 2 cur2 = 2

 第五轮循环：
        left[cur1] > right[cur2]，与第一、第三轮循环相同。此时 left 数组内的 1 个元素能与right[cur2] 构成逆序对，更新 ret 的值，并且将 right[cur2] 加入到辅助数组中去。
第五轮循环结束后：left = [x, x, 9] right = [x, x, x] help = [4, 5, 5, 7, 8] ret = 6 cur1 = 2 cur2 = 2

处理剩余元素：
• 如果是左边出现剩余，说明左边剩下的所有元素都是比右边元素大的，但是它们都是已经被计算过的（我们以右边的元素为基准的），因此不会产生逆序对，仅需归并排序即可。
• 如果是右边出现剩余，说明右边剩下的元素都是比左边大的，不符合逆序对的定义，因此也不需要处理，仅需归并排序即可。

整个过程只需将两个数组遍历一遍即可，时间复杂度为 O(N)。
由上述过程我们可以得出方法一统计逆序对的关键点：
在合并有序数组的时候，遇到左数组当前元素 > 右数组当前元素时，我们可以通过计算左数组中剩余元素的长度，就可快速求出右数组当前元素前面有多少个数比它大，对比暴力解法中一个一个枚举逆序对效率快了许多。

方法二：快速统计出某个数后面有多少个数比它小

2.3 代码实现

这里只写升序版本的代码，感兴趣的话可以自己尝试下降序版本的代码

class Solution {
public:int tmp[50010];int mergeSort(vector<int>& nums,int left,int right){if(left >= right) return 0;int ret = 0;// 1. 找中间点将数组分成两部分int mid = (left+right) >> 1;//[left,mid] [mid+1,right]// 2. 左边的个数 + 右边的个数 + 排序ret += mergeSort(nums,left,mid);ret += mergeSort(nums,mid+1,right);// 3. 一左一右的个数int cur1 = left,cur2 = mid+1, i = 0;while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2])tmp[i++] = nums[cur1++];else{ret += mid-cur1+1;tmp[i++] = nums[cur2++];}}// 处理一下排序while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];//将辅助数组中的值放到nums中for( i = left; i <= right;i++)nums[i] = tmp[i-left];return ret;}int reversePairs(vector<int>& nums) {return mergeSort(nums,0,nums.size()-1);}
};

 

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

3.1 题目

3.2 思路

这一道题的解法与 求数组中的逆序对 的解法是类似的，但是这一道题要求的不是求总的个数，而
是要返回一个数组，记录每一个元素的右边有多少个元素比自己小。
但是在我们归并排序的过程中，元素的下标是会跟着变化的，因此我们需要一个辅助数组，来将数组元素和对应的下标绑定在一起归并，也就是再归并元素的时候，顺势将下标也转移到对应的位置上。
由于我们要快速统计出某一个元素后面有多少个比它小的，因此我们可以利用求逆序对的第二种方法。

算法流程：

• 创建两个全局的数组：
vector<int> index：记录下标
vector<int> ret：记录结果
index 用来与原数组中对应位置的元素绑定，ret 用来记录每个位置统计出来的逆序对的个数。

• countSmaller() 主函数：
        a. 计算 nums 数组的大小为 n；
        b. 初始化定义的两个全局的数组；
                i. 为两个数组开辟大小为 n 的空间
                ii. index 初始化为数组下标；
                iii. ret 初始化为 0
        c. 调用 mergeSort() 函数，并且返回 ret 结果数组。

• void mergeSort( vector<int>& nums, int left, int right ) 函数：
函数设计：通过修改全局的数组 ret， 统计出每一个位置对应的逆序对的数量，并且排序；
无需返回值，因为直接对全局变量修改，当函数结束的时候，全局变量已经被修改成最后的结果。

 • mergeSort() 函数流程：
        a. 定义递归出口：left >= right 时，直接返回；
        b. 划分区间：根据中点 mid，将区间划分为 [left, mid] 和 [mid + 1, right]；
        c. 统计左右两个区间逆序对的数量：
                i. 统计左边区间 [left, mid] 中每个元素对应的逆序对的数量到 ret 数组中，并排序；
                ii. 统计右边区间 [mid + 1, right] 中每个元素对应的逆序对的数量到 ret 数组中，并排序。
        d. 合并左右两个有序区间，并且统计出逆序对的数量：
                i. 创建两个大小为 right - left + 1 大小的辅助数组：
                        • numsTmp： 排序用的辅助数组；
                        • indexTmp：处理下标用的辅助数组。
                ii. 初始化遍历数组的指针：cur1 = left（遍历左半部分数组）cur2 = mid + 1（遍历右半边数组）dest = 0（遍历辅助数组）curRet（记录合并时产生的逆序对的数量）；
                iii. 循环合并区间：
                        • 当 nums[cur1] <= nums[cur2] 时：
                                ◦ 说明此时 [mid + 1, cur2) 之间的元素都是小于 nums[cur1] 的，需要累加到 ret 数组的 indext[cur1] 位置上（因为 index 存储的是元素对应位置在原数组中的下标）
                                ◦ 归并排序：不仅要将数据放在对应的位置上，也要将数据对应的坐标也放在对应的位置上，使数据与原始的下标绑定在一起移动。
                        • 当 nums[cur1] > nums[cur2] 时，无需统计，直接归并，注意 index 也要跟着归并。
                iv. 处理归并排序中剩余的元素；
                        • 当左边有剩余的时候，还需要统计逆序对的数量；
                        • 当右边还有剩余的时候，无需统计，直接归并。
                v. 将辅助数组的内容替换到原数组中去；

 3.3 代码实现

class Solution {
public:vector<int> ret;vector<int> index; //记录nums中的原始下标int tmpNums[500010];int tmpIndex[500010];void mergeSort(vector<int>& nums,int left,int right){if(left >= right) return;// 根据中间元素划分区域int mid = (left+right) >> 1;// [left,mid] [mid+1,right]//先处理左右两部分mergeSort(nums,left,mid);mergeSort(nums,mid+1,right);// 处理一左一右的情况int cur1 = left,cur2 = mid+1, i = 0;while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2]){tmpNums[i] = nums[cur2];tmpIndex[i] = index[cur2];i++; cur2++;}else{ret[index[cur1]] += right-cur2+1;tmpNums[i] = nums[cur1];tmpIndex[i] = index[cur1];i++; cur1++;}}//处理剩下的while(cur1 <= mid) {tmpNums[i] = nums[cur1];tmpIndex[i] = index[cur1];i++; cur1++;}while(cur2 <= right){tmpNums[i] = nums[cur2];tmpIndex[i] = index[cur2];i++; cur2++;}for(int j = left; j <= right; j++){nums[j] = tmpNums[j-left];index[j] = tmpIndex[j-left];}}vector<int> countSmaller(vector<int>& nums) {ret.resize(nums.size());//初始化一下index数组index.resize(nums.size());for(int i = 0; i < nums.size(); i++)index[i] = i;mergeSort(nums,0,nums.size()-1);    return ret;}
};

四、翻转对 

4.1 题目

4.2 思路

翻转对和逆序对的定义大同小异，逆序对是前面的数要大于后面的数。而翻转对是前面的一个数要大于后面某个数的两倍。因此，我们依旧可以用归并排序的思想来解决这个问题。

算法思路：

大思路与求逆序对的思路一样，就是利用归并排序的思想，将求整个数组的翻转对的数量，转换成三部分：左半区间翻转对的数量，右半区间翻转对的数量，一左一右选择时翻转对的数量。重点就是在合并区间过程中，如何计算出翻转对的数量。
与上个问题不同的是，上一道题我们可以一边合并一遍计算，但是这道题要求的是左边元素大于右边元素的两倍，如果我们直接合并的话，是无法快速计算出翻转对的数量的。
例如 left = [4, 5, 6] right = [3, 4, 5] 时，如果是归并排序的话，我们需要计算 left 数组中有多少个能与 3 组成翻转对。但是我们要遍历到最后一个元素 6 才能确定，时间复杂度较高。
因此我们需要在归并排序之前完成翻转对的统计。

下面依旧以一个示例来模仿两个有序序列如何快速求出翻转对的过程：
假定已经有两个已经有序的序列 left = [4, 5, 6] right = [1, 2, 3] 。
用两个指针 cur1 cur2 遍历两个数组。
        ◦ 对于任意给定的 left[cur1] 而言，我们不断地向右移动 cur2，直到 left[cur1] <= 2 *right[cur2]。此时对于 right 数组而言，cur2 之前的元素全部都可以与 left[cur1] 构成翻转对。
        ◦ 随后，我们再将 cur1 向右移动一个单位，此时 cur2 指针并不需要回退（因为 left 数组是升序的）依旧往右移动直到 left[cur1] <= 2 * right[cur2]。不断重复这样的过程，就能够求出所有左右端点分别位于两个子数组的翻转对数目。
由于两个指针最后都是不回退的的扫描到数组的结尾，因此两个有序序列求出翻转对的时间复杂度是 O(N)。
综上所述，我们可以利用归并排序的过程，将求一个数组的翻转对转换成求 左数组的翻转对数量 +右数组中翻转对的数量 + 左右数组合并时翻转对的数量。

4.3 代码实现

class Solution {
public:int tmp[50010];int mergeSort(vector<int>& nums,int left,int right){if(left >= right) return 0;int ret = 0;// 先根据中间元素划分区间int mid = (left + right) >> 1;// [left,mid] [mid+1,right]// 先算出两侧的翻转对ret += mergeSort(nums,left,mid);ret += mergeSort(nums,mid+1,right);// 计算翻转对的数量int cur1 = left, cur2 = mid+1, i = 0;while(cur1 <= mid && cur2 <= right){while(cur2 <= right && nums[cur2] >= nums[cur1]/2.0 ) cur2++;if(cur2 > right) break;ret += right-cur2+1;cur1++;} // 合并两个有序数组cur1 = left,cur2 = mid+1;while(cur1 <= mid && cur2 <= right)tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];for(int j = left; j <= right; j++)nums[j] = tmp[j-left];return ret; }int reversePairs(vector<int>& nums) {return mergeSort(nums,0,nums.size()-1);}
};

 

---

本篇完，下篇见！