算法：分治思想处理归并递归问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法：分治思想处理归并递归问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

算法原理

利用归并思想进行分治也是很重要的一种思路，在解决逆序对的问题上有很大的需求空间

于是首先归并排序是首先的，归并排序要能写出来：

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;
        }
        // 数组划分 [left,mid][mid+1,right]
        int mid=(left+right)/2;

        // 分块排序
        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])
            {
                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 i=left;i<=right;i++)
        {
            nums[i]=tmp[i-left];
        }
    }
};

以上为归并排序基本算法原理，基于这个原理可以解决逆序对问题，逆序对问题通常问法是，给定某一个数据，在整个数组中找比这个数大或者比这个数小的数，统计这样的元素有多少个，进而返回到数组或者直接输出

那么在找寻这个过程中，这类问题的基本思路就是：左边找，右边找，左右找

在找寻的过程中需要注意的是升序和逆序问题，后续的题目中会有涉及到的地方，在这里不过总结

实现思路

大体的实现思路如上，总结下来就是划分为两个子区间，在左边找，在右边找，接着左右找，这样就能找到要求的结果

典型例题

排序数组

算法：分治思想处理归并递归问题,C++,# 算法,习题集,算法,数据结构

理解快速排序和归并排序思维的不同点

依旧是经典的排序数组问题，这次选用归并排序来解决，要了解归并排序和快速排序其实都是利用了分治的思想，把一个很复杂的问题分解为一个一个的小问题，二者在思维上有一些小小的区别，快速排序的思想是，对于某个区间来说，把这个区间进行分块，每一个分块都进行排序，每一个都进行排序，这样就完成了目的，这样的思维更像是一种前序遍历，完成了这次的任务后再向后进行延伸，而归并排序的思路和快速排序不同，归并排序的思路主要是把数组拆分成一个一个的小区间，不停的拆分，直到不能拆分后再进行组装，它的排序过程整体上而言是滞后的，更像是一种后序遍历的思想，先一直向深处找，直到找不下去了再进行排序，再一层一层向上走

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;
        }
        // 数组划分 [left,mid][mid+1,right]
        int mid=(left+right)/2;

        // 分块排序
        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])
            {
                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 i=left;i<=right;i++)
        {
            nums[i]=tmp[i-left];
        }
    }
};

数组中的逆序对

算法：分治思想处理归并递归问题,C++,# 算法,习题集,算法,数据结构
利用归并排序求逆序对是解决这类问题的常见方法，对于这个题来说，就可以采用分治的方法来解决问题

具体来说，可以把整个问题拆分为几个小步骤，把当前所在区间分成两个区间，在左边的区间内找符合逆序对的对数，再在右边的区间内找符合逆序对的对数，同时把左右两区间都进行排序，这样就可以在左右区间内都寻找符合要求的逆序对数，这就是一个轮回思路，把整个数组拆分为一个一个小区间即可解决问题，这就是分治的思想

那么思路就确认了：

从左边数组中找符合要求的逆序对
从右边数组中找符合要求的逆序对
从左右两边数组中找符合要求的逆序对

从排列组合的分类原理来看，这样就能找到所有的逆序对

从优化角度来讲，第三步是可以进行优化的，这就引入了要排序的原因：

如何从左右两数组中找逆序对数？

其实利用双指针的思想就可以解决，定义cur1和cur2分别指向左右两个数组，假设这里是提前排序好的，升序的数组，那么当cur1所指向的元素大于cur2所指的元素，那么cur2所指向的元素之前的元素全部满足条件，因此一次可以找出很多相同的元素，这也是这个算法的原理

因此这里就引出了为什么要进行排序，左右子区间排序后就可以通过上面的算法快速找到有多少满足要求的逆序对

处理剩余元素

如果是左边出现剩余，说明左边剩下的所有元素都是⽐右边元素⼤的，但是它们都是已经被计算过的，因此不会产⽣逆序对，仅需归并排序即可。
如果是右边出现剩余，说明右边剩下的元素都是⽐左边⼤的，不符合逆序对的定义，因此也不需要处理，仅需归并排序即可。

class Solution 
{
    vector<int> tmp;
public:    

    int reversePairs(vector<int>& nums) 
    {
        tmp.resize(50001);
        return mergesort(nums,0,nums.size()-1);
    }

    int mergesort(vector<int>& nums,int left,int right)
    {
        if(left>=right)
        {
            return 0;
        }

        int ret=0,mid=(left+right)/2;

        ret+=mergesort(nums,left,mid);
        ret+=mergesort(nums,mid+1,right);

        int cur1=left,cur2=mid+1,i=0;
        while(cur1<=mid && cur2<=right)
        {
            if(nums[cur1]<=nums[cur2])
            {
                tmp[i++]=nums[cur1++];
            }
            else
            {
                ret+=mid-cur1+1;
                tmp[i++]=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];
        }

        return ret;
    }
};

总体来说还是一道有思维量的hard题目，但如果掌握了分治的思想，再去下手就会容易许多

而这样的算法的时间复杂度也是很优秀的，时间复杂度是O(N)

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

算法：分治思想处理归并递归问题,C++,# 算法,习题集,算法,数据结构

有了上面的题目的思维铺垫，解法还是比较好想的，原理就是利用归并排序进行分治的思想

但这个题和上面的问题也有区别，由于返回的是数组，因此需要记录nums中每一个数组中元素在返回数组中元素的下标，需要一一对应起来，这是比较关键的一步，也就是说，每次找到符合条件的数后，这个数应该被放到返回数组中的哪个位置？这就需要用一个辅助数组来记录原数组中每一个元素的下标所在的位置，这样就能找到了

class Solution 
{
    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);
        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;
        }

        int mid=(left+right)/2;
        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=left;j<=right;j++)
        {
            nums[j]=tmpnums[j-left];
            index[j]=tmpindex[j-left];
        }
    }
};