C++算法 —— 分治（2）归并

---

本篇前提条件是已学会归并排序

1、排序数组

912. 排序数组

排序数组也可以用归并排序来做。

    vector<int> tmp;//写成全局是因为如果在每一次小的排序中都创建一次，更消耗时间和空间，设置成全局的就更高效vector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());mergeSort(nums, 0, nums.size() - 1);return nums;}//归并做法void mergeSort(vector<int>& nums, int left, int right){if(left >= right) return ;int mid = (left + right) / 2;mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);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(int i = left; i <= right; i++){nums[i] = tmp[i - left];}}

2、数组中的逆序对

剑指 Offer 51. 数组中的逆序对

如果暴力枚举，一定是可以解决问题的，但肯定不用这个解法。选择逆序对，可以先把数组分成两部分，左半部分 + 右半部分的逆序对，以及再找左半部分的数字和右半部分数字成对的数，比如上面例子中，7和6，7和4就是这种情况。左 + 右 + 一左一右就是整体的逆序对数量。当这两半部分都处理完后，就扩大区间，继续上述操作。这个解法也就是利用归并排序，归并排序的思路就是划分到最小的区间，只有1个数，它一定是有序的，回到上一层，也就是2个数的区间，让它们排好序，在它右边的也是2个数的区间，重复和它一样的操作，这样两个区间都有序后，再往上走一层，来到4个数的区间，4个数，每一半都是有序的，将整体的4个数排成有序的，再往上走，来到8个数的区间，重复操作。

利用归并排序的思路，我们在两个区间都排成升序后，定义两个指针cur指向两个区间的开头，然后一左一右比较大小，如果cur1比cur2大，那么cur1之后都比cur2大，就可以一次性加上多个逆序对的个数。

下面的代码可以从最小的区间开始一个个代入来理解。从只有2个数的区间开始，走到递归处，分成2个只有1个数的区间，那就会返回0，两处递归走完，来到下面的循环，此时left是0，right是1，mid是0，带入进去会发现，最后的ret只会是0或者1，并且这2个数也在最后排好序了，返回后，来到上一层，也就是走左边递归的那行代码，然后再走右边，也是2个数，也是同样的操作，2个区间排好序了，4个数的区间就一左一右比较大小，找出逆序对，排好序，再走到上一层，8个数的区间也是如此。

class Solution {int tmp[50010];
public:int reversePairs(vector<int>& nums) {return mergeSort(nums, 0, nums.size() - 1);}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)//while体内原本是归并排序的代码，现在就多加一点{if(nums[cur1] <= nums[cur2]) tmp[i++] = nums[cur1++];else{ret += mid - cur1 + 1;tmp[i++] = nums[cur2++];}}//4. 处理排序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;}
};

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

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

此题和上一个题有相同之处，也是分治，也是利用归并排序，这道题可以看作，当前元素后面，有多少比我小的，而上一题则是当前元素前面，有多少比我大的。仔细想一想，上一题是排升序，这一题排降序则更为合适。这题和上一题还有不同的地方。

cur1和cur2，排成降序，如果cur1 <= cur2，cur2++，因为我们要找比当前元素小的；如果cur1 > cur2，由于是降序，那么cur2之后的肯定都小，但这里不能加上ret，我们要返回一个数组，要把这个数加在当前元素的原始下标，因为数组已经被我们给排序了，所以要找原始下标。这里的做法就是从最一开始就除了tmp外，再定义一个数组，存储着原始下标，因为这时候还没开始排序，可以找得到，然后每次原数组元素变换位置，这个下标数组也跟着变换。

我们要定义四个数组，一个是结果数组，一个是原始下标数组，一个是辅助数组，也就是tmp，记录改动过的顺序，一个是下标辅助数组，记录改动后的下标顺序。在while循环中，每次更新tmp，下标辅助数组也跟着更新。如果cur1大于cur2，那么除了更新，还需要往结果数组中写入个数，要在当前元素的原始下标处写入个数，这里最好要画图来理解，画原始下标和下标变动后的图。在最后for循环中的排序，除了原数组nums，还有原始下标数组也要排序。

    vector<int> index;//原始元素下标vector<int> res;//最终结果int tmp[500010];//排序辅助数组int tmpIndex[500010];//元素下标的辅助数组
public:vector<int> countSmaller(vector<int>& nums) {int sz = nums.size();index.resize(sz);res.resize(sz);for(int i = 0; i < sz; i++){index[i] = i;}mergeSort(nums, 0, sz - 1);return res;}void mergeSort(vector<int>& nums, int left, int right){if(left >= right) return ;int mid = (left + right) >> 1;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]){tmp[i] = nums[cur2];tmpIndex[i++] = index[cur2++];}else {res[index[cur1]] += right - cur2 + 1;//经历了之前的排序，index已经记录下了最新的下标变动，这里就可以直接用cur1来获取正确的下标tmp[i] = nums[cur1];tmpIndex[i++] = index[cur1++];}}while(cur1 <= mid){tmp[i] = nums[cur1];tmpIndex[i++] = index[cur1++];}while(cur2 <= right){tmp[i] = nums[cur2];tmpIndex[i++] = index[cur2++];}for(int j = left; j <= right; j++){nums[j] = tmp[j - left];index[j] = tmpIndex[j - left];}}

4、翻转对

493. 翻转对

还是一样的思路。左半部分，右半部分，然后一左一右。不过这里的条件不一样。这里的解决办法有两个，一个是计算当前元素后面有多少元素的两倍比我小，另一个是计算当前元素之前，有多少元素的一半比我大，这两个的高效顺序分别是降序和升序。

第一个思路，cur1和cur2，找当前元素的后面，那就以cur1为重点，如果cur2的2倍大于等于cur1，cur2就往后走，如果小于，那么后面的肯定都小于。第二个思路，cur1和cur2，找当前元素的前面，那就以cur2为重点，如果cur1的一半比cur2小，那么cur1后的肯定都符合条件，如果cur1的一半大于cur2，那cur1往后走。最后合并两个有序数组。

    int tmp[50010];
public:int reversePairs(vector<int>& nums) {return mergeSort(nums, 0, nums.size() - 1);}int mergeSort(vector<int>& nums, int left, int right){if(left >= right) return 0;int ret = 0;int mid = (left + right) >> 1;ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right); int cur1 = left, cur2 = mid + 1, i = left;//先计算翻转对，0还是left都行/*while(cur1 <= mid)//这里排降序，也可以排升序{while(cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;//2.0是为了防止除不尽if(cur2 > right) break;ret += right - cur2 + 1;cur1++;}*/while(cur2 <= right)//升序{while(cur1 <= mid && nums[cur2] >= nums[cur1] / 2.0) cur1++;if(cur1 > mid) break;ret += mid - cur1 + 1;cur2++;}cur1 = left, cur2 = mid + 1;//归位一下，开始排序while(cur1 <= mid && cur2 <= right){tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];//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];}return ret;}

结束。