【算法】分治 · 归并

【ps】 本篇有 4 道 leetcode OJ。 

目录

一、算法简介

二、相关例题

1）排序数组

.1- 题目解析

.2- 代码编写

2）交易逆序对的总数

.1- 题目解析

.2- 代码编写

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

.1- 题目解析

.2- 代码编写

4）翻转对

.1- 题目解析

.2- 代码编写

一、算法简介

        与快速排序类似，归并排序也将无序数组进行划分，根据数组的中间位置，通过递归的方式依此将数组划分为两个区间，直到每个区间只有一个元素为止，然后在每一层递归对划分后的数组进行排序，最终递归层层返回，将若干个排好序的小区间合并起来，这样就完成了对无序数组的排序。

二、相关例题

1）排序数组

912. 排序数组

.1- 题目解析

        本题作为归并排序的模板性质的例题，来向读者展示归并的实现过程，详见下小节的代码和注释。

【Tips】归并排序的实现步骤

1. 取中点；
2. 根据中点划分左右区间进行排序；
3. 合并排完序的左右区间（具体方式是将有序的元素先放到一个临时数组中，再将临时数组赋给原数组）。

.2- 代码编写

class Solution {vector<int> 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;//2.划分区间进行排序//[left, mid] [mid + 1, right]mergeSort(nums,left,mid);   //划分左区间，对左区间进行排序        mergeSort(nums,mid+1,right);//划分右区间，对右区间进行排序//3.合并排好序的左右区间int cur1=left,cur2=mid+1; //分别负责遍历排好序的左右区间int 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）交易逆序对的总数

LCR 170. 交易逆序对的总数

.1- 题目解析

        在数组中任意固定一个数，只要这个数之后的数比它小，它就能跟它们组成逆序对。

        逆序对由两个依此递减的数组成，我们可以由此将数组也分为两部分，每个部分都进行升序排列，这样的话，从右边部分中选定一个数，只要它比左边部分的一个数大，那它就比左边部分这个数之后的数都要大，它都可以和它们构成逆序对。而这个过程很符合归并排序的特性，就可以利用归并排序来完成。

.2- 代码编写

class Solution {vector<int> tmp;
public:int reversePairs(vector<int>& nums) {tmp.resize(nums.size());return mergeSort(nums,0,nums.size()-1);}int mergeSort(vector<int>& nums,int left,int right){if(left>=right)return 0;//1.取中点，划分左右区间int mid=(left+right)>>1;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+=cur1-left+1; //左边的一个数比右边的一个数小，它之前的数比右边的都小，在此统计这一些逆序对的个数tmp[i++]=nums[cur2++];//合并完右边的一个数后，继续比较它的下一个数}}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. 计算右侧小于当前元素的个数

.1- 题目解析

        这道题与上一道题类似，只不过返回的数组里是，原数组中相应下标的元素右侧，比它小的元素的个数。

         为了将统计的结果放到返回数组中的正确下标位置，我们还需要将原数组的下标保存一份。

.2- 代码编写

class Solution {vector<int> ret;  //存放结果vector<int> index;//存放原数组中元素的原始下标int Ntmp[500010];//合并时的元素辅助数组，负责存放原数组的元素int Itmp[500010];//合并时的下标辅助数组，负责存放原数组元素的下标public:vector<int> countSmaller(vector<int>& nums) {ret.resize(nums.size());index.resize(nums.size());for (int i = 0; i < nums.size(); i++)index[i] = i;mergeSort(nums, 0, nums.size() - 1);return ret;}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]) {Ntmp[i] = nums[cur2];Itmp[i] = index[cur2];//合并时，不仅要将元素放入元素辅助数组，还要将其下标也放入下标辅助数组i++;cur2++;} else {ret[index[cur1]] += right - cur2 + 1;//左边的一个数比右边的一个数大，则它比右边之后的数都要大，此时就可以统计结果了//将结果统计到左边的数的下标位置上（因为我们以左边的数为基准在右边找小于它的个数）Ntmp[i] = nums[cur1];Itmp[i] = index[cur1];i++;cur1++;}}while (cur1 <= mid) {Ntmp[i] = nums[cur1];Itmp[i] = index[cur1];i++;cur1++;}while (cur2 <= right) {Ntmp[i] = nums[cur2];Itmp[i] = index[cur2];i++;cur2++;}for (int j = left; j <= right; j++) {nums[j] = Ntmp[j - left];index[j] = Itmp[j - left];}}
};

4）翻转对

493. 翻转对

.1- 题目解析

        这道题与上文中的题类似，也可以用归并的方式，将数组分成左右两部分进行比较即可。

        由于比较的是一倍大于二倍，因此比较要在合并排序之前进行。

.2- 代码编写

class Solution {int tmp[50010];
public:int reversePairs(vector<int>& nums) {int n=nums.size();int ret=mergeSort(nums,0,n-1);return ret;}int mergeSort(vector<int>& nums,int left,int right){if(left>=right)return 0;//1.取中点划分数组int ret=0;int mid=(left+right)>>1;//2.计算左右部分的翻转对+排序ret+=mergeSort(nums,left,mid);ret+=mergeSort(nums,mid+1,right);int cur1=left,cur2=mid+1,i=0;//3.计算翻转对while(cur1<=mid){while(cur2<=right && nums[cur2]>=nums[cur1]/2.0)cur2++;if(cur2>right)break;ret+=right-cur2+1;cur1++;}//4.合并两个有序数组cur1=left,cur2=mid+1;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;j<=right;j++)nums[j]=tmp[j-left];return ret;}
};