算法日记分治：用归并排序解决逆序对问题

🎬 胖咕噜的稞达鸭：个人主页

🔥 个人专栏: 《数据结构》《C++初阶高阶》
《Linux系统学习》
《算法日记》⛺️技术的杠杆，撬动整个世界!

---

剑指Offer.数组中逆序对

https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/

--------------------------------- left mid mid+1 right

利用归并排序解决该问题。
策略一：找出该数之前，有多少个数比我大，

1.nums[cur1] <= nums[cur2] cur1++ 2.nums[cur1] > nums[cur2] ret+=mid - cur1 + 1;cur2++

刚才算法中，数组是升序的，
如果数组是降序的，该怎么做？不能用策略一。
策略二：
可以用降序做，找出该数之后，有多少个数比我小

nums[cur1] > nums[cur2] ret += right - cur2 + 1 nums[cur1] <= nums[cur2] cur2++

方法一：用升序数组来解决这道题

classSolution{inttmp[50001];public:intreversePairs(vector<int>&nums){returnmergeSort(nums,0,nums.size()-1);}intmergeSort(vector<int>&nums,intleft,intright){if(left>=right)return0;//1.找中间点intmid=(left+right)>>1;intret=0;//2.左边的个数(paixu)加上右边的个数 + 排序ret+=mergeSort(nums,left,mid);ret+=mergeSort(nums,mid+1,right);//3.一左一右的个数intcur1=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++];}}//4.处理排序的while(cur1<=mid)tmp[i++]=nums[cur1++];while(cur2<=right)tmp[i++]=nums[cur2++];for(intj=left;j<=right;j++)nums[j]=tmp[j-left];returnret;}};

方法二：用降序数组来解决这道题

classSolution{inttmp[50001];public:intreversePairs(vector<int>&nums){returnmergeSort(nums,0,nums.size()-1);}intmergeSort(vector<int>&nums,intleft,intright){if(left>=right)return0;//1.找中间点intmid=(left+right)>>1;intret=0;//2.左边的个数(paixu)加上右边的个数 + 排序ret+=mergeSort(nums,left,mid);ret+=mergeSort(nums,mid+1,right);//3.一左一右的个数intcur1=left,cur2=mid+1,i=0;while(cur1<=mid&&cur2<=right){if(nums[cur1]<=nums[cur2]){tmp[i++]=nums[cur2++];}else{ret+=right-cur2+1;tmp[i++]=nums[cur1++];}}//4.处理排序的while(cur1<=mid)tmp[i++]=nums[cur1++];while(cur2<=right)tmp[i++]=nums[cur2++];for(intj=left;j<=right;j++)nums[j]=tmp[j-left];returnret;}};