算法 | 归并排序、求逆序对

排序数组（归并排序）

题解：

交易逆序对的总数

题解：

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

题解：

翻转对

题解：

排序数组（归并排序）

912. 排序数组 - 力扣（LeetCode）https://leetcode.cn/problems/sort-an-array/description/

题解：

归并排序就是把数组不断分组，分到不能再分的时候，开始两两一组进行排序。可以根据实际，选择排序后数组为升序或降序。

mid = left + (right - left) /2 可以防止 mid 溢出。

在辅助数组排完序后，要把数字填回原来的数组。

class Solution {
public: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-left)/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[cur2++]:nums[cur1++]);while(cur1<=mid)    tmp[i++]=nums[cur1++];while(cur2<=right)  tmp[i++]=nums[cur2++];for(int j=left,i=0;j<=right;j++) nums[j]=tmp[i++];   }};

交易逆序对的总数

LCR 170. 交易逆序对的总数 - 力扣（LeetCode）https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/

题解：

合并阶段本质上是合并两个排序数组的过程，而每当遇到左子数组当前元素 > 右子数组当前元素时，意味着左子数组当前元素至末尾元素与右子数组当前元素构成了若干逆序对 。

比如下图，cur1 < cur2 显然成立，且左右子数组皆为升序，

当 record[ cur1 ] > record[ cur2 ] 时，record[ cur1 ] 和 record[ cur2 ] 构成逆序对，又 cur1 右边的数大于等于 record[ cur1 ] ，所以 cur1 右边的数和 record[ cur2 ] 也构成逆序对！逆序对的总数加上 mid - cur1 +1.
当 record[ cur1 ] <= record[ cur2 ] 时，说明当前访问的数不构成逆序对，cur1++，往后遍历。

在判断完逆序对之后，要进行升序排序，便于下一层遍历时找逆序对。

class Solution {
public:vector<int> tmp;int reversePairs(vector<int>& record) {tmp.resize(record.size());return mergeSort(record,0,record.size()-1);//左闭右闭}int mergeSort(vector<int>& record,int left,int right){if(left>=right) return 0;int ret=0,mid=left+(right-left)/2;ret+=mergeSort(record,left,mid);ret+=mergeSort(record,mid+1,right);//边合并边计数,排升序int cur1=left,cur2=mid+1,i=0;while(cur1<=mid && cur2<=right){if(record[cur1]<=record[cur2])   tmp[i++]=record[cur1++];else{ret+=(mid-cur1+1);  tmp[i++]=record[cur2++];}}while(cur1<=mid)   tmp[i++]=record[cur1++];while(cur2<=right)  tmp[i++]=record[cur2++];for(int j=left,i=0;j<=right;j++)    record[j]=tmp[i++];return ret;}
};

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

315. 计算右侧小于当前元素的个数 - 力扣（LeetCode）https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/

题解：

由于归并排序后有些数字已经不再原来的位置了，这不便于我们把统计出来的逆序对放到对应的位置，所以需要设置一个下标数组，记录数组元素的初始下标。若数组中存在重复的数字，但是下标不同，哈希表无法处理这种映射关系，用数组解决即可。

如下图，在归并排序的基础上，更新数字下标的位置。

class Solution {
public:vector<int> ret;vector<int> tmpIndex;//临时数组的下标vector<int> index;//原数组元素的下标vector<int> tmpNums;//临时数组vector<int> countSmaller(vector<int>& nums) {int n=nums.size();tmpIndex.resize(n);   tmpNums.resize(n);index.resize(n);  ret.resize(n);for(int i=0;i<n;i++)  index[i]=i;//初始化mergeSort(nums,0,n-1);//左闭右闭return ret;}void mergeSort(vector<int>& nums,int left,int right){if(left>=right) return;int mid=left+(right-left)/2;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++];}else//右侧比当前大，计数且排序{ret[index[cur1]]+=(right-cur2+1);tmpNums[i]=nums[cur1];tmpIndex[i++]=index[cur1++];}}while(cur1<=mid)   {tmpNums[i]=nums[cur1];tmpIndex[i++]=index[cur1++];}while(cur2<=right){tmpNums[i]=nums[cur2];tmpIndex[i++]=index[cur2++];}//填回原数组for(int j=left,i=0;j<=right;j++)    {nums[j]=tmpNums[i];   index[j]=tmpIndex[i++];}}
};

翻转对

493. 翻转对 - 力扣（LeetCode）https://leetcode.cn/problems/reverse-pairs/description/

题解：

求逆序对的判断条件和归并排序一样，所以把它们写在同一个 while 循环中，但是翻转对的判断条件和归并排序的判断不同，我们需要在归并排序前计算翻转对的个数。

2*nums[cur2]>=nums[cur1] 写成 nums[cur2]>=nums[cur1]/2.0 是为了防止溢出！

class Solution {
public:vector<int> tmp;int reversePairs(vector<int>& nums) {int n=nums.size();  tmp.resize(n);return mergeSort(nums,0,n-1);//左闭右闭}int mergeSort(vector<int>& nums,int left,int right){if(left>=right) return 0;int ret=0,mid=left+(right-left)/2;ret+=mergeSort(nums,left,mid);ret+=mergeSort(nums,mid+1,right);int cur1=left,cur2=mid+1,i=0;//找翻转对while(cur1<=mid){while(cur2<=right && nums[cur2]>=nums[cur1]/2.0)    cur2++;if(cur2>right)  break;//没有必要遍历了ret+=(right-cur2+1);    cur1++;}//合并,排降序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 j=left,i=0;j<=right;j++,i++)    nums[j]=tmp[i];return ret;}
};