【优选算法】---分治 归并排序

一、排序数组 / 归并排序的复习

归并排序的主要步骤：

①：就是找一个数组里面的中间数mid，将这个数组分为两部分，左半部分和右半部分。然后再从左半部分和右半部分里面再找一个中间数mid，依次不断的递归下去，直到分到最小单位为止，排完序之后从下往上返回，这就是归并排序的递归。
②：合并两个有序数组（双指针法）
分别对左半部分数组和右半部分数组，定义一个下标移动的变量cur1和cur2，然后进行循环比较。

1、题目解析

题目链接：排序数组

2、算法原理

分治的思想：归并排序类似于二叉树的后序遍历

主要步骤：

1. 中间点的划分
2. 对左右区间的递归
3. 合并两个有序数组
4. 还原

3、代码

class Solution 
{vector<int> tmp;// (2)第二种方法，在全局开一个临时数组tmp(用来保存每次递归合并的两个有序数组)，//  然后就不用每次递归还创建tmp
public: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;// 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++];// 4、还原for(int i=left;i<=right;i++){nums[i]=tmp[i-left];}}};

二、逆序对的总数

1、题目解析

数组中的逆序对 链接

2、算法原理

（1）将整个数组分为左半部分和右半部分，
（2）分别在左半部分找逆序对的个数，排完序。
（3）然后再在右半部分找逆序对的个数再排排序，
（4）最后再一左一右利用双指针的算法，固定一个然后移动另外一个在：一左一右->这两个数组里面分别找逆序对的个数，最后加起来就是整个数组的逆序对个数。

这样的解法的时间复杂度：N*logN

关键的细节：

3、代码

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;// 1、找中间值mid划分为左右两部分int mid=(left+right)>>1;// [left,mid]  [mid+1,right]int ret=0;// 记录逆序对个数// 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+=cur2-(mid+1)+1;  这种情况不行，因为我们是以左边为基准的，只要cur1遍历完，一左一右这个过程就结束了！ret+=mid-cur1+1;// 因为是升序，所以在左半部分，只要此时的cur1>cur2，那么位于cur1右侧~mid之间的数据全部>cur2tmp[i++]=nums[cur2++];}}// 3、处理没遍历完的while(cur1<=mid) tmp[i++]=nums[cur1++];while(cur2<=right) tmp[i++]=nums[cur2++];// 4、还原for(int j=left;j<=right;j++){nums[j]=tmp[j-left];// 始终不太理解 还原的时候，为啥要用j-left？？？不能直接nums[j]=tmp[j]吗？？？}return ret;}
};

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

1、题目解析

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

2、算法原理

这道题仍然是利用归并排序的分治思想

但是这次我们要排的是：降序！

但是有一点需要特别注意，这是一个重点也是一个难点。

题目中需要返回的是一个数组！
一个什么样的数组呢？原始数组下标所对应位置，有多少个右面比我小的元素。

这里的重点和难点就在于：我们如何找到我们正在遍历的数组（是打乱排完序的）中当前元素的原始下标！

解决办法就是：在进行分治归并排序之前，对原始数组利用哈希思想进行下标绑定。

就是你进行递归排序的时候，你的下标跟着你的数字是一起移动的！！！

3、代码

class Solution 
{vector<int> ret;// 返回答案的数组vector<int> index;// 创建index数组的原因是：对排序前的 原始数组 进行下标“绑定”！int tmpNums[500010];// 这两个都是临时数组int tmpIndex[500010];
public:vector<int> countSmaller(vector<int>& nums) {int n=nums.size();ret.resize(n);index.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 ;// 1、找中间数midint 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){// 降序排序if(nums[cur1]<=nums[cur2]){tmpNums[i]=nums[cur2];tmpIndex[i++]=index[cur2++];}else{//tmpNums[index[i]]+=right-cur2+1;// 重点！(统计此时cur1位置有多少符合条件的，因为cur1原本是在nums中遍历的，但是由于，index跟nums是一一对应的关系，所以index[cur1]就代表着原始数据的下标)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++];}// 4、还原for(int j=left;j<=right;j++){nums[j]=tmpNums[j-left];index[j]=tmpIndex[j-left];}}
};

四、翻转对

1、题目解析

链接：翻转对

2、算法原理

主要思想还是用归并排序的分治思想

1、运用递归分别：处理左半部分、右半部分
2、运用“ 单调性+同向的双指针 ” 处理一左一右的情况

3、代码

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、中间数midint mid=(left+right)>>1;// 2、处理左半部分、右半部分ret+=mergeSort(nums,left,mid);ret+=mergeSort(nums,mid+1,right);// 3、一左一右(固定cur1不动，cur2移动)int cur1=left,cur2=mid+1,i=left;while(cur1<=mid){while(cur2<=right&&nums[cur1]/2.0<=nums[cur2])// 因为 *2会溢出，所以我们用/2.0{cur2++;}// 接下来就是符合条件的ret+=right-cur2+1;cur1++;}// 4、合并两个有序数组cur1=left,cur2=mid+1;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++];// 4、还原for(int j=left;j<=right;j++){nums[j]=tmp[j];}return ret;}
};