深度解析算法之分治（归并）

48.排序数组

题目链接
给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例 1：

输入： nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入： nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

我们上次解决这个问题是使用快排进行解决的，那么这里是使用归并排序进行解决的

归并是什么呢？说白了就是递归
将一个数组根据中间点分成两部分，我们再从左边区间找中间点，依次这样，直到我们最后只剩下一个元素，我们依次进行返回的操作，然后进行上一层的右区间进行递归递归
当我们这一层的判断都搞定了，那么我们就进行合并两个有序数组

当我们左边和右边都排完序之后，那么我们就将这两个有序数组进行合并操作

这种非常像二叉树的后续遍历，先把左边搞好，再把右边搞好，再回到根节点
快排的过程有点类似二叉树的前序遍历

class Solution{public:    vector sortArray(vector& nums)    {        mergesort(nums,0,nums.size()-1);//将这段区间进行排序，排完序直接返回就行了        return nums;    }    void mergesort(vector&nums,int left,int right)    {        if(left>=right) return;//特殊情况，如果区间不存在或者是只有一个元素的话         //1.先选择中间点划分区间        int mid=(left+right)>>1;// >> 1 是位运算中的右移操作，它将结果右移一位，相当于将结果除以2并向下取整。        //[left,mid][mid+1,right]        //2.将左右区间进行排序的操作        mergesort(nums,left,mid);        mergesort(nums,mid+1,right);         //3.合并两个有序数组        vectortmp(right-left+1);//辅助数组，大小和我们的nums大小一样        int cur1=left;//指向第一个数组        int cur2=mid+1;//指向第二个数组        int i=0;//辅助数组         while(cur1<=mid&&cur2<=right)        {            tmp[i++]=nums[cur1]<=nums[cur2]?nums[cur1++]:nums[cur2++];//进行判断，如果cur1的大小小于等于cur2的话，那么就让我们的tmp[i]=nums[cur1]的值            //就是说白了持续进行对比，谁小谁先放到tmp这个数组中去            //i、cur1、cur2这三个指针都得往后进行移动，我们直接放在上面的那个代码中去        }        //到这里的话可能存在一个数组中还有数据没有移动到tmp中去，下面两句代码就是处理没有遍历完的情况        while(cur1<=mid)tmp[i++]=nums[cur1++];//因为此时的指针还没到mid的位置，就是大小比mid小，那么我们直接将cur1这个数字中剩下的元素都放到tmp中        while(cur2<=right)tmp[i++]=nums[cur2++];//和上面一样         //还原        for(int i=left;i<=right;i++)        {            nums[i]=tmp[i-left];//我们的tmp数组需要从0开始进行计数操作吗，所以我们这里使用i-left可以达到从下标0开始进行赋值操作        }     } };

我们先找出中间点对这段数组进行划分操作，然后依次对左右区间进行排序的操作，这里就是递归调用，然后我们再合并两个数组就行了
最后我们将我们辅助数组中的值直接赋值到我们的nums中就行了

这种代码我们的时间复杂度是这样的

因为我们每次合并的时候都会创建一个辅助数组，这里的开销其实也很大的

我们可以将创建数组的这个操作放在全局的位置

class Solution{    vectortmp;//创建辅助数组public:    vector sortArray(vector& nums)    {        tmp.resize(nums.size());        mergesort(nums,0,nums.size()-1);//将这段区间进行排序，排完序直接返回就行了        return nums;    }    void mergesort(vector&nums,int left,int right)    {        if(left>=right) return;//特殊情况，如果区间不存在或者是只有一个元素的话         //1.先选择中间点划分区间        int mid=(left+right)>>1;// >> 1 是位运算中的右移操作，它将结果右移一位，相当于将结果除以2并向下取整。        //[left,mid][mid+1,right]        //2.将左右区间进行排序的操作        mergesort(nums,left,mid);        mergesort(nums,mid+1,right);         //3.合并两个有序数组        int cur1=left;//指向第一个数组        int cur2=mid+1;//指向第二个数组        int i=0;//辅助数组         while(cur1<=mid&&cur2<=right)        {            tmp[i++]=nums[cur1]<=nums[cur2]?nums[cur1++]:nums[cur2++];//进行判断，如果cur1的大小小于等于cur2的话，那么就让我们的tmp[i]=nums[cur1]的值            //就是说白了持续进行对比，谁小谁先放到tmp这个数组中去            //i、cur1、cur2这三个指针都得往后进行移动，我们直接放在上面的那个代码中去        }        //到这里的话可能存在一个数组中还有数据没有移动到tmp中去，下面两句代码就是处理没有遍历完的情况        while(cur1<=mid)tmp[i++]=nums[cur1++];//因为此时的指针还没到mid的位置，就是大小比mid小，那么我们直接将cur1这个数字中剩下的元素都放到tmp中        while(cur2<=right)tmp[i++]=nums[cur2++];//和上面一样         //还原        for(int i=left;i<=right;i++)        {            nums[i]=tmp[i-left];//我们的tmp数组需要从0开始进行计数操作吗，所以我们这里使用i-left可以达到从下标0开始进行赋值操作        }     } };

这里我们可以看看时间开销

如果在递归中需要创建空间的话，那么我们就将这个操作放在全局上

49.数组中的逆序对

题目链接
在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。

输入一个数组，求出这个数组中的逆序对的总数。

数据范围

给定数组的长度 [0,100][0,100]。

样例

输入：[1,2,3,4,5,6,0]输出：6

暴力解法：暴力枚举
两层for循环就能暴力出所有的情况，但是会超时的

我们求出一个中心点，将整个数组分成两段，分别进行判断 ，递归进行求

利用归并排序解决该问题

逆序对就是一个数之前有多少个数比自身大，那么就有多少组逆序对
那么我们盯着cur2这个区域看就行了
因为我们这里经过了排序了，所以两个区域都是升序的，
如果nums[cur1]<=nums[cur2]的话，那么就让cur1++
如果nums[cur1]>nums[cur2]的话，因为区域是升序的吗，所以当前cur1后面的都是比cur2大的数字，所以我们就找到了一堆的逆序数，所以我们的逆序数总和就加上了mid-cur1+1

所以这个题利用归并排序的话时间复杂度就是nlogn

我们这个题是升序的，如果是降序的话这个题怎么做呢？
如果nums[cur1]>nums[cur2]的话，那么我们就统计cur1前面的区域，然后我们将cur1++，但是如果此时的nums[cur1]>nums[cur2]，那么我们就会出现重复计算的问题了
如果我们将原先的策略改成：找出某个数之后，有多少个数比较小，然后我们此时就可以利用到了这个降序操作了
如果我们当前cur1大于cur2的话，因为这个是降序的，所以cur2后面的都比cur2小，所以我们找到比cur1小的数就行了，那么cur2后面一大堆比cur1小的，统计完当前数中有多少个数比cur1小的，然后我们的cur1进行右移操作

下面是数组为升序的版本

class Solution{ int tmp[999999];//创建一个辅助数组进行数组合并的public: int inversePairs(vector& nums) { return mergeSort(nums,0,nums.size()-1);//将0~n-1这段区间的逆序对都找到 } int mergeSort(vector&nums,int left,int right) { if(left>=right) return 0;//处理特殊情况，这个区间没有逆序对或者是 只存在一个元素的话 int ret=0;//记录最终的结果 //1.找一个中间点 int mid=(right+left)>>1; //划分为下面的两个区间了 //[left,mid][mid+1,right] //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 //这个就是cur1的数大于cur2的数 { ret+=mid-cur1+1; tmp[i++]=nums[cur2++];//将小的放进去 } } //4.处理下排序,将剩下的元素放进去 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; }};

归并排序的第一步是递归地将数组拆分成越来越小的子数组，直到每个子数组只有一个元素为止。这个过程是通过 mergeSort(nums, left, mid) 和 mergeSort(nums, mid + 1, right) 完成的。每次递归都会找到数组的中间点 mid，然后对左右两部分递归调用 mergeSort。

在归并的过程中，我们将左右两个子数组合并成一个已排序的数组。在这个过程中，如果左侧的某个元素大于右侧的某个元素，那么这些元素就构成了逆序对。

剩余元素处理：
如果在合并的过程中，某一侧的数组已经处理完了，而另一侧仍然有元素剩余，这时剩下的元素已经是有序的，因此可以直接将它们放入到 tmp 数组中，不需要做任何比较。

将排序后的元素放回原数组：
合并完成后，我们将 tmp 数组中的元素复制回 nums 数组，这样在上层递归中会使用到最新排序好的数组。

下面是降序的代码

class Solution{ int tmp[999999];//创建一个辅助数组进行数组合并的public: int inversePairs(vector& nums) { return mergeSort(nums,0,nums.size()-1);//将0~n-1这段区间的逆序对都找到 } int mergeSort(vector&nums,int left,int right) { if(left>=right) return 0;//处理特殊情况，这个区间没有逆序对或者是 只存在一个元素的话 int ret=0;//记录最终的结果 //1.找一个中间点 int mid=(right+left)>>1; //划分为下面的两个区间了 //[left,mid][mid+1,right] //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[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(int j=left;j<=right;j++) { nums[j]=tmp[j-left]; } return ret; }};

改动的代码在这里

50.计算右侧⼩于当前元素的个数

题目链接
给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

示例 1：

输入： nums = [5,2,6,1]
输出： [2,1,1,0] 解释
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

示例 2：

输入： nums = [-1]
输出：[0]

示例 3：

输入： nums = [-1,-1]
输出：[0,0]

有点像我们的逆序对
使用归并排序

我们需要快速求出当前元素右边有多少个元素比当前元素小
我们这里使用策略二：当前元素右边元素有多少个比我小

如果nums[cur1]<=nums[cur2]的话，那么我们的cur2得往右边进行挪动了
但是如果nums[cur1]>nums[cur2]的话，那么我们就得将nums[cur1]在统计数的那个数组中的对应的位置加上我们有多少个小于cur2的位置的数了，所以我们得找到cur1的原始下标了，我的思路是使用hash，但是如果出现了重复元素的话就不好搞了
我们再创建一个数组，存的是我们原始的下标，一起进行绑定移动就行了

我们这里是需要创建两个辅助数组的，一个是nums合并的辅助数组
一个是原始下标的辅助数组

class Solution{    vectorret;    vectorindex;//记录当前元素的原始下标    int tmpNums[500010];//nums的辅助数组    int tmpIndex[500010];//index的辅助数组public:    vector countSmaller(vector& nums)    {        int n=nums.size();        ret.resize(n);        index.resize(n);         //初始化index数组        for(int i=0;i<n;i++)        {            index[i]=i;        }        mergerSort(nums,0,n-1);        return ret;    }    void mergerSort(vector&nums,int left,int right)    {        //先处理边界情况        if(left>=right) return ;//要么这个数组只有一个元素，要么就是没有元素         //1.根据中间元素划分区间        int mid=(right+left)>>1;        //[left,mid][mid+1,right]         //2.先处理左右两部分        mergerSort(nums,left,mid);        mergerSort(nums,mid+1,right);         //3.处理一左一右的情况        int cur1=left,cur2=mid+1,i=0;        while(cur1<=mid&&cur2<=right)//降序数组        {            if(nums[cur1]nums[cur2]            {                //index[cur2]就是cur2当前的下标                ret[index[cur1]]+=right-cur2+1;//重点，先找到原始位置的下标,我们这里统计的是cur1位置后面的数有多少个比cur1小                tmpNums[i]=nums[cur1];                tmpIndex[i++]=index[cur1++];            }        }         //3.处理排序剩下的排序过程        while(cur1<=mid) //说明我们的cur1还有预留的数据，那么我们将剩下的数据全部放到我们的辅助数组中去        {            tmpNums[i]=nums[cur1];            tmpIndex[i++]=index[cur1++];        }        while(cur2<=right) //说明我们的cur1还有预留的数据，那么我们将剩下的数据全部放到我们的辅助数组中去        {            tmpNums[i]=nums[cur2];            tmpIndex[i++]=index[cur2++];        }        //还原        for(int j=left;j<=right;j++ )        {            nums[j]=tmpNums[j-left];            index[j]=tmpIndex[j-left];        }     }};

求当前位置的右边有多少个数比cur1小的。所以我们这里是降序的，将大的元素先进行移动到辅助数组中去

51.翻转对

题目链接
给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个 重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

示例 1:

输入: [1,3,2,3,1]
输出: 2

示例 2:

输入: [2,4,3,5,1]
输出: 3

找两个数，前面的数是大于后面的那个数的两倍的

策略一：计算当前元素后面，有多少元素的两倍比我小 降序
我们发现cur2位置的两倍的大小比cur1小，那么cur2后面的数字的两别都比cur1小

计算翻转对->同向双指针

策略二：计算当前元素之前，有多少元素的一半比我大 升序
我们这里移动cur1，如果cur1的一半比cur2小的话，那么cur1右移
当我们发现cur1的一半比cur2大的话，那么cur1后面的一半都比cur2大
下面是降序的代码

class Solution{    int tmp[50010];//辅助数组，帮助我们合并排序public:    int reversePairs(vector& nums)    {        return mergeSort(nums,0,nums.size()-1);    }     int mergeSort(vector&nums,int left,int right)    {        if(left>=right) return 0;//处理异常情况         int ret=0;          //1.先根据中间元素划分区间        int mid=(right+left)>>1;        //[left,mid][mid+1,right]         //2.先计算左右两侧的翻转对        ret+=mergeSort(nums,left,mid);        ret+=mergeSort(nums,mid+1,right);         //3.先计算翻转对的数量        int cur1=left,cur2=mid+1,i=left;        while(cur1<=mid)//降序        {            while(cur2=nums[cur1]/2.0) cur2++;//向后进行移动，直到找到合适的位置            if(cur2>right) break;//如果满足了越界的情况了，那么我们直接break就行了            //出了循环就说明我们找到对应的位置了            ret+=right-cur2+1;            cur1++;//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++];         //5.还原        for(int j=left;j<=right;j++)        {            nums[j]=tmp[j];        }        return ret;    }};

我们先根据中间元素划分区间，然后计算左右两侧的翻转对，这个就是递归调用函数
然后计算翻转对的数量，然后合并两个有序数组，最后就是还原了
。

这里计算翻转对的数量，我们让我们的cur1不动，cur一直往后移动，直到遇到了满足条件的，就是nums[cur2]>=nums[cur1]/2.0的话，那么我们就将cur2后面这段区间进行累加到ret中去，然后再去移动cur1进行下一组的判断，循环结束之后，我们的翻转对的数量就计算出来了

这个时候我们得将当前的这段和别的段进行合并，就是合并两个有序数组的操作，直接合并在tmp这个辅助数组中，合并完成之后可能会有一组数组还有剩余的数据，我们将这些数据放到我们的tmp中去
最后我们需要将原先的数组进行还原操作
为什么需要进行还原操作？
在递归过程中，原始数组 nums 的数据会被拆分成许多子数组，且每个子数组都在递归过程中经过合并操作。在合并过程中，我们将排好序的子数组的元素合并到辅助数组 tmp 中。如果不还原回来，nums 数组就无法保持正确的排序顺序，也无法准确地反映最终的排序结果

我们使用升序的代码进行解决问题
升序就是找当前元素之前有多少个数比我大， 所以此时固定的就是cur2了

class Solution{    int tmp[50010];//辅助数组，帮助我们合并排序public:    int reversePairs(vector& nums)    {        return mergeSort(nums,0,nums.size()-1);    }     int mergeSort(vector&nums,int left,int right)    {        if(left>=right) return 0;//处理异常情况         int ret=0;          //1.先根据中间元素划分区间        int mid=(right+left)>>1;        //[left,mid][mid+1,right]         //2.先计算左右两侧的翻转对（递归调用操作）        ret+=mergeSort(nums,left,mid);        ret+=mergeSort(nums,mid+1,right);         //3.先计算翻转对的数量        int cur1=left,cur2=mid+1,i=left;        while(cur2<=right)//升序        {            while(cur1=nums[cur1]/2.0) cur1++;//向后进行移动，直到找到合适的位置            if(cur1>mid) break;//如果满足了越界的情况了，那么我们直接break就行了            //出了循环就说明我们找到对应的位置了            ret+=mid-cur1+1;            cur2++;//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++];         //5.还原        for(int j=left;j<=right;j++)        {            nums[j]=tmp[j];        }        return ret;    }};