【算法学习】分治篇：分治算法的类型和解题详解

算法学习：.html?spm=1001.2014.3001.5482

前言：

分治算法在平时做题中应用还是非常广泛的，下面我们从分治——快排和分治——归并两个角度来讲一下分治算法的核心

1. 分治算法的原理

分治，顾名思义，就是分而治之，将一个比较大的问题分成若干个较小的子问题，这样划分的前提一般都是子问题与父问题之间存在某种联系，能够通过相同或相似的解法来解决，主要的应用就体现在快排和归并排序上，下面我们通过一些经典例题来感受一下分治的魅力

2. 经典例题

下面的这些题都是力扣上的题，可以看完之后自己去刷一遍

2.1 分治——快排

2.1.1 颜色划分

75. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

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

示例 2：

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

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

我们先来看一下题，题意简单点来说就是分类，将0、1、2三个数分类合在一起，这与有一个移动0的操作非常相似，不同的是那个题是将两个数分类，那个题用的是双指针，类比，这个题我们可以用三指针来操作，下面我们来看一下如何用三指针来解这道题

解释:

• 我们这里维护了三个指针，left,right和i，其中left左侧全是0，right右侧全是2，i则是代表当前检测的位置
• 通过上面三个指针的作用，整个数组其实是被划分成四个区间，从左到右依次是:全是0、全是1、待扫描、全是2
• 当i向右走的时候，如果遇到0，它就需要将这个数移到left所在的区间，方法就是让left++，并把left所在位置数与i所在位置数交换后让i也++;
• 当遇到1时不做处理，i++即可;
• 当遇到2时，让right--，同时交换这两个位置的值但是不能让i++，因为交换到i位置的这个数是未被扫描过的

代码实现：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left=-1,right=nums.size(),i=0;
        while(i<right)
        {
            if(nums[i]==1) i++;
            else if(nums[i]==0) swap(nums[++left],nums[i++]);
            else swap(nums[--right],nums[i]);
        }
    }
};

2.1.2 排序数组

912. 排序数组

给你一个整数数组 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]

提示：

• 1 <= nums.length <= 5 * 104
• -5 * 104 <= nums[i] <= 5 * 104

算法原理：

解释: 这里我们要实现的快排的核心与上一题很像，都是通过三指针的方法，将数组分为三块，但是这里有几个需要特别注意的点:

代码实现：

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        srand(time(NULL));
        qsort(nums,0,nums.size()-1);
        return nums;
    }
    void qsort(vector<int>& nums,int l,int r)
    {
        if(l>=r) return;
        int key=getRandom(nums,l,r);
        int i=l, left=l-1, right=r+1;
        while(i<right)
        {
            if(nums[i]<key) swap(nums[++left],nums[i++]);
            else if(nums[i]==key) i++;
            else swap(nums[--right],nums[i]);
        }
        qsort(nums,l,left);
        qsort(nums,right,r);
    }
    int getRandom(vector<int>& nums,int left,int right)
    {
        int r=rand();
        return nums[r%(right-left+1)+left];
    }
};

2.1.3 数组中第k个最大元素

215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

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

示例 2:

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

提示：

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

算法原理：

代码实现：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(NULL));
        return qsort(nums,0,nums.size()-1,k);
    }
    int qsort(vector<int>& nums,int l,int r,int k)
    {
        if(l==r) return nums[l];

        int key=nums[rand()%(r-l+1)+l];
        int left=l-1,right=r+1,i=l;
        while(i<right)
        {
            if(nums[i]<key) swap(nums[++left],nums[i++]);
            else if(nums[i]==key) i++;
            else swap(nums[i],nums[--right]);
        }
        int a=left-l+1,b=right-left-1,c=r-right+1;
        if(k<=c) return qsort(nums,right,r,k);
        else if(k<=b+c) return key;
        else return qsort(nums,l,left,k-b-c);
    }
};

2.2 分治——归并

归并排序核心思想:

归并排序操作就是先取一个中间值，然后让左右两侧的数组继续进行这种划分操作，直到每一个分组只有一个数组的时候，让它们向上进行合并，合并的时候要进行大小排序

快排：

快排和归并排序其实挺相似的，都要进行数组分块的操作，不同的是分块的时机不同，归并排序是先进行分组，在后面合并时才进行排序，快排是每一次分块前都按照基准元素进行排序，然后才分组 归并排序有点类似二叉树的后序遍历，而快排则类似于前序遍历

2.2.1 排序数组

912. 排序数组

还是上面那道题，只不过这里我们用归并的方法再来实现一遍

我们直接来看代码吧，归并排序的原理就是我们上面所说的那样，下面我们结合代码和注释再来思考一下：

这就是归并排序的代码实现，在写下面的归并排序的题之前，一定要先将归并排序的实现搞明白简单点来说就是要先递归，当每个分组只有一个数时往上返回，并且进行排序

代码实现：

class Solution {
public:
    vector<int> tmp;
    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)/2;
        //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[cur2++]:nums[cur1++];
        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];
    }
};

2.2.2 交易逆序对的总数

LCR 170. 交易逆序对的总数

在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。

示例 1：

输入：record = [9, 7, 5, 4, 6]
输出：8
解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。

提示：

0 <= record.length <= 50000

解释:

• 根据这个图解，我们思考一下，如果我们在归并排序中，将数组分为(3，4，5)和(2，6，7)两部分，当进行合并排序时，我们发现此时后边的2小于3，因为左边也是这样处理过来的且已经进行排序了，所以2肯定小于左边所有的数，所以逆序对数直接加上左半边所有的个数，按照这样的方式一直递归，直到排为有序的
• 同时在解这道题的时候我们可以从两个视角来看这道题，其一是找出一个数之前有多少数比它大这个需要我们在排序时按照升序来排，另一个就是找出一个数之后有多少个数比它小，这个按照降序来排，升序和降序的代码相差不大

代码实现：

class Solution {
    int tmp[50010];
public:
    int reversePairs(vector<int>& record) {
        return mergesort(record,0,record.size()-1);
    }
    int mergesort(vector<int>& record,int l,int r)
    {
        if(l>=r) return 0;
        int ret=0;
        //1. 找中间点将数组分为两部分
        int mid=(l+r)>>1;
        //2. 左边的个数+排序+右边的个数+排序
        ret+=mergesort(record,l,mid);
        ret+=mergesort(record,mid+1,r);
        //3. 一左一右的个数
        int cur1=l,cur2=mid+1,i=0;
        while(cur1<=mid&&cur2<=r)
        {
            if(record[cur1]<=record[cur2]) tmp[i++]=record[cur1++];
            else{
                ret+=(mid-cur1+1);
                tmp[i++]=record[cur2++];
            }
        }
        //4. 处理一下排序
        while(cur1<=mid) tmp[i++]=record[cur1++];
        while(cur2<=r) tmp[i++]=record[cur2++];
        for(int j=l;j<=r;j++)
            record[j]=tmp[j-l];
        return ret;
    }
};

2.2.3 翻转对

493. 翻转对

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

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

示例 1:

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

示例 2:

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

注意:

1. 给定数组的长度不会超过50000。
2. 输入数组中的所有数字都在32位整数的表示范围内。

算法原理：

这道题与前面计算逆序对个数的题挺像，但是还是有所不同在计算逆序对的时候我们在进行数组排序的过程中就能计算逆序对的个数，因为判断条件是一样的，但是这个题不行 比如当我们按照降序排序时: 排序的条件:nums[left]<=nums[right] 计算翻转对的条件:nums[left]<=nums[right]*2 也就是说它们的判定条件不同，所以需要在不同的循环中进行，所以我们可以先计算逆序对的个数，然后再进行排序

排序时可以按照升序和降序两种方式:

• 升序:计算当前元素之前，有多少数一半比我大
• 降序:计算当前元素之后，有多少数二倍比我小

如果我们将排序和计算翻转对数量放在一起，乍一看好像挺对，但实际上是有问题的比如数组:{5，4，3，2，1}

我们看上面的过程，cur1指向的数为5，它大于2的两倍，因为是按照降序排序的，所以它肯定也大于2右侧的数字，所以ret+=right-cur2+1，计算过后我们就需要把5先放入tmp数组中，然后再看4，4不大于2的两倍，所以ret不变，然后把4放入tmp数组中，此时就出现了问题，因为4虽然不大于2的两倍，但是它大于2的两倍，也就是说4没有与2右侧的数进行比较，就因为排序的条件的限制进入了tmp数组中了，所以我们需要把这两步分开处理

代码实现：

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;
        int mid=(left+right)>>1;
        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]/2.0<=nums[cur2]) cur2++;
            else{
                ret+=right-cur2+1;
                cur1++;
            }
        }
        //重置指针，然后将排序完成
        cur1=left,cur2=mid+1;
        while(cur1<=mid&&cur2<=right)
        {
            if(nums[cur1]<=nums[cur2]) tmp[i++]=nums[cur2++];
            else{                
                tmp[i++]=nums[cur1++];
            }
        }
        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;
    }
};

3. 总结

以上就是有关分治的主要应用及经典例题的详解，各位在看后可以自己再去做一遍

本篇笔记：

感谢各位大佬观看，创作不易，还望各位大佬点赞支持！！！