【优选算法】D&C-Mergesort-Harmonies：分治-归并的算法之谐
文章目录
本篇是优选算法之分治-归并，简单来说就是一个不断分组排序再合并的过程
1.概念解析
🚩什么是分治-归并？
分治归并（基于分治思想的归并排序）是分治算法（Divide and Conquer）在排序问题中的经典应用，核心是通过 “拆分 - 排序 - 合并” 三步，将无序数组转化为有序数组，本质是 “化繁为简、再合简为繁” 的解题思路
2.排序数组
✏️题目描述：
✏️示例：
传送门：排序数组
题解:
本质上分治归并就是一个后序遍历，而快排就是一个前序遍历，不断向下细分数组，然后从下往上把左右两分支的数组排序并合并，以此向上循环往复
💻细节问题：
int mid = left + ((right - left) >> 1)相当于int mid = left + ((right - left) / 2)，二进制的算法效率更高，且该计算中间值的方法能避免整数溢出- 最后一步合并数组，
nums[left + j] = tmp[j]而不是nums[j] = tmp[j]，是因为left不一定是0，即不一定是对原来的整个数组进行排序，可能只对数组一部分进行排序 - 数组排序并不影响逆序对的计算，因为是左右两部分比较，内部已经在递归过程中计算过了
💻代码实现：
#include<iostream>#include<vector>usingnamespace std;classSolution{ vector<int> tmp;public: vector<int>sortArray(vector<int>& nums){ tmp.resize(nums.size());mergeSort(nums,0, nums.size()-1);return nums;}voidmergeSort(vector<int>& nums,int left,int right){if(left >= right){return;}int mid = left +((right - left)>>1);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 j =0; j <= right - left;++j){ nums[left + j]= tmp[j];}}};3.交易逆序对的总数
✏️题目描述：
✏️示例：
传送门：交易逆序对的总数
题解:
因为归并排序的 “分治 + 有序合并” 特性，完美匹配逆序对统计的核心需求 —— 高效拆分问题、批量计算逆序对，这是暴力枚举做不到的，当 [left,mid] 和 [mid+1,right] 进行互相比较时，如果是升序，获取到 record[cur1] >= record[cur2] 时，由于是有序，所以 cur2 往后都是小于 cur1 对应的数的，所以能直接得到很多对逆序数。用降序也是同理
💻代码实现：
classSolution{ vector<int> tmp;public:intreversePairs(vector<int>& record){ tmp.resize(50010);returnmergeSort(record,0, record.size()-1);}intmergeSort(vector<int>&record,int left,int right){if(left >= right){return0;}int ret =0;int mid = left +((right - left)>>1); 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 =0; j < right - left +1;++j){ record[j + left]= tmp[j];}return ret;}};4.计算右侧小于当前元素的个数
✏️题目描述：
✏️示例：
传送门：计算右侧小于当前元素的个数
题解:
这题和上一题思路基本一致，唯一的难点就是要额外创建一个数组进行值和下表的绑定，因为题目要求的是返回每个 index 对应的值，有人就问了为什么不能用哈希表，可以是可以但是有重复值的话会很麻烦，因此额外创建一个数组进行 index 和值的绑定更方便，index 数组跟着 nums 数组移动就行
💻代码实现：
classSolution{ vector<int> ret; vector<int> index;int tmpNums[500010];int tmpindex[500010];public: vector<int>countSmaller(vector<int>& nums){int n = nums.size(); ret.resize(n,0); index.resize(n);for(int i =0; i < n;++i){ index[i]= i;}mergeSort(nums,0, n -1);return ret;}voidmergeSort(vector<int>& nums,int left,int right){if(left >= right){return;}int mid = left +((right - left)>>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]){ 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 =0; j < right - left +1;++j){ nums[j + left]= tmpNums[j]; index[j + left]= tmpindex[j];}}};5.翻转对
✏️题目描述：
✏️示例：
传送门：翻转对
题解:
思路还是利用归并解决，但是要提前计算符合题目要求的翻转对，如果在排序过程中进行计算，会漏掉部分翻转对
💻细节问题：
(long long)nums[cur1] <= 2 * (long long)nums[cur2] 防止溢出
💻代码实现：
classSolution{ vector<int> tmp;int ret =0;public:intreversePairs(vector<int>& nums){ tmp.resize(nums.size());mergeSort(nums,0, nums.size()-1);return ret;}voidmergeSort(vector<int>& nums,int left,int right){if(left >= right){return;}int mid = left +((right - left)>>1);mergeSort(nums, left, mid);zq mergeSort(nums, mid +1, right);int cur1 = left, cur2 = mid +1, i =0;while(cur2 <= right){while(cur1 <= mid &&(longlong)nums[cur1]<=2*(longlong)nums[cur2]){ cur1++;}if(cur1 > mid){break;} ret += mid - cur1 +1; cur2++;} cur1 = left, cur2 = mid +1;while(cur1 <= mid && cur2 <= right){if(nums[cur1]<= nums[cur2]){ tmp[i++]= nums[cur1++];}else{ tmp[i++]= nums[cur2++];}}while(cur1 <= mid){ tmp[i++]= nums[cur1++];}while(cur2 <= right){ tmp[i++]= nums[cur2++];}for(int j =0; j < right - left +1;++j){ nums[j + left]= tmp[j];}}};希望读者们多多三连支持
小编会继续更新
你们的鼓励就是我前进的动力！
