第一步肯定还是要弄懂什么是分治归并思想，这个思想最经典的地方也就是归并排序的实现了。那么我们现在就来复习一下归并排序的实现方法。
首先归并排序的第一步也就是分治，例如上图将数组中的元素不断的划分直到每一个元素都被划分成单独的一个一个之后再将其不断地合并直到最后完成归并排序。
题目1：排序数组
下面是代码实现：
class Solution {
public:
void merge(vector<int>& nums, int begin, int mid, int end, vector<int>& tmp) {
int leftbegin = begin;
int rightbegin = mid + 1;
int tmpbegin = begin;
while (leftbegin <= mid && rightbegin <= end) {
//这里需要一个tmp数组来帮助我们再排序完数组之后将数组返回到原数组
if (nums[leftbegin] < nums[rightbegin]) {
tmp[tmpbegin++] = nums[leftbegin++];
} else {
tmp[tmpbegin++] = nums[rightbegin++];
}
}
while (leftbegin <= mid) {
tmp[tmpbegin++] = nums[leftbegin++];
}
while (rightbegin <= end) {
tmp[tmpbegin++] = nums[rightbegin++];
}
for (int i = begin; i <= end; i++) {
nums[i] = tmp[i];
}
}
void mergeSort(vector<int>& nums, int begin, int end, vector<int>& tmp) {
//这一个函数地目的便是不断地将数组进行二分
if (begin >= end) {
return;
}
int mid = (begin + end) / 2;
mergeSort(nums, begin, mid, tmp);
mergeSort(nums, mid + 1, end, tmp);
merge(nums, begin, mid, end, tmp);//二分完之后这个函数地目的为对函数进行合并
}
vector<int> sortArray(vector<int>& nums) {
vector<int> tmp(nums.size());
mergeSort(nums, 0, nums.size() - 1, tmp);
return tmp;
}
};题目2：数组中的逆序对
题目链接：剑指 Offer 51. 数组中的逆序对 - 力扣（LeetCode）
题目地要求虽然很简单但是要在不超时地情况下完长还是比较难的。很明显若要在规定的时间内完成，那么肯定是要使用分治归并的思想来解决的问题在于如何去运用这个思想，并且为什么使用这个思想能够完成。首先我们在完成归并排序的时候我们想到如果将待排序的数组分成两个部分，并且这两个部分都变成有序之后，在让这两个数组合并自然也就能得到一个有序的数组，那么我们依旧沿用这个思想。假设现在有一个长度为n的数组，并且已经被分成了两个部分并且两个部分的元素都已经是有序的（升序）了。下面就请看下图来解决这个问题。
上图解释了使用分治归并元素解决这个问题的思想（当然我这里只分析了排序后是升序的情况也可以是降序）。下面我们来解释为什么可以，因为在解释中我说过当分治完成之后，左半部分和右半部分的逆序对已经记录完毕并且已经排完序了，那么左半部分和右半部分是什么时候完成这个工作的呢？答案就是在归并的途中就完成了。和归并排序一样，归并排序也是会将每一个元素都会分割成一个一个单独的个体，然后再合并，那么这里也是一样的，也会将数组中的元素全部分割成一个一个的元素，然后将每一个单独的元素都认为是单独的左半部分和右半部分，寻找一次逆序对，这样就能够保证整个数组都是能够纳入计算的。
下面是代码的实现：
class Solution {
public:
//这一个版本为左右数组中的元素为降序的情况
void find_same(vector<int>& nums,vector<int>& tmp,int begin,int mid,int end,int& ret)
{
int leftbegin = begin;
int rightbegin = mid+1;
int tmpi = begin;//作为tmp数组的下标
while(leftbegin<=mid&&rightbegin<=end)
{
if(nums[leftbegin]<=nums[rightbegin])
{
tmp[tmpi++] = nums[rightbegin++];
}
//当找到一个rightbegin中对应的数是比leftbegin小的话，从rightbegin开始到end这一段的所有数都是比leftbegin小的
else//在这里是rightbegin>leftbegin
{
tmp[tmpi++] = nums[leftbegin];
ret+= end - rightbegin+1;//找到了此时大于rightbegin的所有的数目的个数，此时这些数的个数也就是好数对的数目
leftbegin++;
}
}
while(leftbegin<=mid)
{
tmp[tmpi++] = nums[leftbegin++];
}
while(rightbegin<=end)
{
tmp[tmpi++] = nums[rightbegin++];
}
//最后要将这道题给排序完成
for(int i = begin;i<=end;i++)
{
nums[i] = tmp[i];
}
}
void _reversePairs(vector<int>& nums,vector<int>& tmp,int begin,int end,int& ret)
{
if(begin>=end)
{
return;
}
int mid = (begin+end)/2;
_reversePairs(nums,tmp,begin,mid,ret);
_reversePairs(nums,tmp,mid+1,end,ret);//将数组分成两个部分
//第三个部分合并的同时要统计逆序对的数目
find_same(nums,tmp,begin,mid,end,ret);//合并并且去寻找逆序对
}//
int reversePairs(vector<int>& nums) {
//题目思路和归并排序的思路很相似
int ret = 0;//统计逆序对的数目
vector<int> tmp(50010);//创建一个临时数组
_reversePairs(nums,tmp,0,nums.size()-1,ret);
return ret;
}
};//这里我使用了一个ret去储存逆序对的数目题目2：计算右侧小于当前元素的个数
题目链接：315. 计算右侧小于当前元素的个数 - 力扣（LeetCode）
这道题目我们依旧是沿用上面那道题目的方法，在完成左右的分治之后就已经把左半部分和右半部分元素在当前区域内按照题目要求的元素个数已经求出来了，并且完成排序了，下面是要处理左半部分和右半部分。和上一道题目不同的是这一道题目使用降序排列时跟简单的（升序也能写），这里就之提出降序的思路了，假设依旧是left和right指针，当出现right<left的时候就找到了right往后的所有元素都是小于left的，然后让left++，right++，假设是right>=left那就让right++。
这里我就不画图解释了，和上一道题几乎是一摸一样的。
但是还有一个问题就是我们肯定要使用一个数组来储存每一个元素对应的答案的，但是没经过一次递归遍历元素的位置都会发生变化，所以这里我们就需要再来一个额外的数组用来储存当前的元素所在的下标。以上图的例子1为例子，nums[5] = 5 2 6 1 ，那么这里我们就需要一个额外的数组，来储存当前这个位置的元素的下标index[5] = 0 1 2 3 4，当nums里面的元素移动的时候index里面的元素一起移动假设移动成了 2 5 6 1，那么index也会变成 1 0 2 3 4，那么这样就能够保证要返回答案的数组能够精准的找到当前元素在未移动前的位置。
下面是代码的实现：
class Solution {
public:
void merge_sort(vector<int>& nums,int begin,int end,vector<int>& tmp1,vector<int>& tmp2,vector<int>& ret,vector<int>& index)
{
if(begin>=end)
{
return ;
}//确定递归的返回条件
int mid = (begin+end)>>1;
merge_sort(nums,begin,mid,tmp1,tmp2,ret,index);//分治左半部分并且完成排序
merge_sort(nums,mid+1,end,tmp1,tmp2,ret,index);//分治右半部分并且完成排序
//下面再来进行合并
//这里的tmp2数组就是为了确保index数组里面的元素能够和nums数组一样的进行移动
//而做的临时数组
int leftbegin = begin;
int rightbegin = mid+1;
int tmp1i = begin;
int tmp2i = begin;//作为tmp1和tmp2数组的下标
while(leftbegin<=mid&&rightbegin<=end)
{
if(nums[leftbegin]<=nums[rightbegin])
{
tmp1[tmp1i++] = nums[rightbegin];
tmp2[tmp2i++] = index[rightbegin++];
}
else
{
tmp1[tmp1i++] = nums[leftbegin];
tmp2[tmp2i++] = index[leftbegin];
ret[index[leftbegin]] += end - rightbegin+1;
leftbegin++;
}
}
while(leftbegin<=mid)
{
tmp1[tmp1i++] = nums[leftbegin];
tmp2[tmp2i++] = index[leftbegin++];//同时要更新的是一个和nums绑定的数组
}
while(rightbegin<=end)
{
tmp1[tmp1i++] =nums[rightbegin];
tmp2[tmp2i++] = index[rightbegin++];
}
//最后要合并数组
for(int i = begin;i<=end;i++)
{
nums[i] = tmp1[i];
index[i] = tmp2[i];
}
}
vector<int> countSmaller(vector<int>& nums) {
vector<int> index(nums.size());//创建一个数组这个数组中的每一个数都代表了nums中的每一个数的下标
for(int i = 0;i<nums.size();i++)
{
index[i] = i;//nums中的第i个数在nums中的下标
//index数组中的下标i代表的是nums中的第i个数（0代表第一个数）然后index里面储存的就是这个数在nums[i]中的下标
}
vector<int> ret(nums.size());//用于记录和返回答案的数组
//下面要使用
vector<int> tmp1(nums.size());//一个用于辅助index的合并
vector<int> tmp2(nums.size());//一个用于辅助nums的合并
merge_sort(nums,0,nums.size()-1,tmp1,tmp2,ret,index);
return ret;
}
};题目3：翻转对
题目链接：翻转对
这道题目的思路和上面的两道也是差不多的，但是区别在于之前两道题目我们都可以在数组放到tmp过程中去判断答案，但是这道题不行，因为判断的条件是nums[i] > 2*nums[j],也即是左半部分的元素大于右半部分元素的两倍。这和放到tmp数组的条件（nums[j] > nums[i]（升序）/nums[i]>nums[j]（降序））是冲突的。所以这里我们要在将两个部分的数组合并之前就判断得到答案。
下面是代码实现：
class Solution {
public:
void _reversePairs(vector<int>& nums, vector<int>& tmp, int begin, int end, int& ret)
{
if (begin >= end)
{
return;
}//确定递归终止条件
int mid = (begin + end) >> 1;
_reversePairs(nums, tmp, begin, mid, ret);
_reversePairs(nums, tmp, mid + 1, end, ret);
//由此就将数组分成了两个部分，并且两个部分都已经把各自的逆序对给计算出来了
//下面需要先计算翻转对的数目，在进行合并，我这里使用的是降序
int leftbbegin = begin, rightbegin = mid + 1;
//由此就完成了降序状态下翻转对的计算
//这里要使用同向双指针
while (leftbbegin <= mid)
{
while (rightbegin <= end)
{
//因为题目给出的数据在乘上一个2倍之后可能会超出int的范围所以这里使用了/
if (nums[leftbbegin]/2.0 > nums[rightbegin])
{
ret += end - rightbegin + 1;
break;
}
else
{
rightbegin++;
}
}
leftbbegin++;
}
//下面要将两个部分的数组有序合并
int tmpi = begin;
leftbbegin = begin;
rightbegin = mid + 1;
while (leftbbegin <= mid && rightbegin <= end)
{
if (nums[leftbbegin] >= nums[rightbegin])
{
tmp[tmpi++] = nums[leftbbegin++];
}
else
{
tmp[tmpi++] = nums[rightbegin++];
}
}
while (leftbbegin <= mid)
{
tmp[tmpi++] = nums[leftbbegin++];
}
while (rightbegin <= end)
{
tmp[tmpi++] = nums[rightbegin++];
}
for (int i = begin; i <= end; i++)
{
nums[i] = tmp[i];
}
}
int reversePairs(vector<int>& nums) {
//思路为分治+同向双指针
vector<int> tmp(nums.size());//创建一个临时数组，用于合并两个分开的数组
int ret = 0;//记录翻转对的数目
_reversePairs(nums, tmp, 0, nums.size() - 1, ret);//寻找从0到nums.size()-1位置存在多少组翻转对
return ret;
}
};因为还是一个在学习的人，文章内容写的不好，请见谅，如果发现了任何错误，请指出，感激不尽。