自学内容网 自学内容网

【基础算法总结】分治--快排+归并

一,分治算法介绍

分治是一类十分重要的算法,"分治"顾名思义就是分而治之,把一个大问题分成若干个相同或是相似的子问题 ,再把这些小问题继续划分成若干个相同或是相似的更小子问题…直到最小子问题不可再划分。接着通过解决最小子问题进而解决了上一层更小子问题…又进而解决了大问题。这个过程就是 – 递归

我们学过的快速排序和归并排序就是非常典型也是非常重要的分治。但是它们的分治思想不仅仅用于排序上,在解决其他问题时也是非常有效的。下面介绍的若干道题目就是使用快排和归并的核心思想解决的,让大家加深对它们的理解

二,算法原理和代码实现

75.颜色划分

在这里插入图片描述
在这里插入图片描述

这道题十分经典,它的代码是快速排序的核心代码之一(因为快排有多种实现方式,核心代码也有多种),它的本质就是数组分三块(数组划分)
本题是为下面几题做铺垫的,不是用分治算法,而是使用三指针
(1) 首先是三个指针的作用:
i:遍历扫描数组,初始化为0
left:标记0区域的最右侧,初始化为-1
right:标记2区域的最左侧,初始化为最后一个元素的下一个位置
(2) 这三个下标把数组分为4部分:
[0,left] :全是0
[left+1,i-1]:全是1
[i,right-1]:待扫描的元素
[right, n-1]:全是2
在这里插入图片描述
(3) 在扫描过程中:
a. 当arr[i] == 0时:swap(arr[++left],arr[i++]),把0放入指定区域,并完成指针移动
b. 当arr[i] == 1时:i++
c. 当arr[i] == 2时:swap(arr[–right],arr[i]),把2放入指定区域,但是i不能移动,因为交换后 i 所指的依旧是待扫描的
(4) 当 i 与 right 相遇后,待扫描区间不存在了,此时遍历结束

代码实现:

class Solution 
{
public:
    void sortColors(vector<int>& nums)
    {
        int n = nums.size();
        int left = -1, right = n, i = 0;
        // 当i >= right时,说明待扫描区域已经扫描完了,可以结束了
        while(i < right)
        {
            if(nums[i] == 0) swap(nums[++left], nums[i++]);
            else if(nums[i] == 1) i++;
            else swap(nums[--right], nums[i]);
        }
    }
};

912.排序数组-快速排序

在这里插入图片描述
在这里插入图片描述

算法原理:

这道题可以使用我们以前学过的快速排序的算法(二路快排)解决,但是当数据中有很多重复值时,使用以前的算法时间复杂度会退化成 O(N^2)
我们上一题介绍的"数组分三块"(三路快排)的思想就可以很好的解决这个问题,原因是当数组里的数据都是 key 时,进行一次划分后就变成一块区域了(就是等于key的,没有大于或是小于key的),此时没有左右区间,就不用进行递归了,直接结束。这里的时间复杂度是 O(N) 级别

这里还可以进行优化:用随机的方式选择基准元素
在这里插入图片描述

代码实现:

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]);
        }
        
// 走完一遍"数组分三块"时,i与right已经重合了
        // [l, left] [left+1, right-1] [right, r]
        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];
    }
};

215.数组中的第k个最大元素(快速选择算法)

在这里插入图片描述
在这里插入图片描述

topK问题是一类很重要的问题,一般有4种问法
a. 找第K大
b. 找第K小
c. 找前K大
d. 找前K小
解决这类问题有两种算法:
(1) 堆结构 – O(N * logN)
(2) 快速选择算法(基于快排) – O(N)

算法原理:

这道题是基于上一题的快排算法内容,由前文可知,基准值 key 把数组分为三块区域,从左往右依次是小于key,等于key,大于key。所以我们只需要确定本题中要找的的第 k 大元素落在哪个区域,就在哪块区域里找,其余两块区域不需要再考虑了

所以接下来的重点就是要讨论如何确定第 k 大元素落在哪个区域
假设数组中的三块区域的元素的个数分别是 a,b,c。分三种情况讨论
在这里插入图片描述
(1) 如果是落在最右边的区域,则 c >= k
此时只需要去 [right, r] 区域,继续找第 k 大元素就好了

(2) 如果是落在中间的区域,则 b+c >= k
此时第 k 大元素一定是在中间的区域,直接返回 key 即可

(3) 如果(1)(2)都不成立,此时要去 [l, left] 区域,找第 k-b-c 大的元素

代码实现:

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 = getRandom(nums, l, r);
        
        // 数组分三块
        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[--right], nums[i]);
        }

        // 分情况讨论
        int c = r - right + 1, b = right - left -1;
        if(c >= k) return qsort(nums, right, r, k);
        else if(b + c >= k) return key;
        else return qsort(nums, l, left, k-b-c);
    }

    int getRandom(vector<int>& nums, int left, int right)
    {
        return nums[rand() % (right - left + 1) + left];
    }
};

LCR159.最小的k个数(快速选择算法)

在这里插入图片描述
在这里插入图片描述

算法原理:

这道题也是一道topk问题,解法也有多种:一是直接排序,再取出前k个元素,时间复杂度O(N * ogN)二是使用堆结构,时间复杂度O(N * logN)三是使用快速选择算法,时间复杂度O(N)

这里只介绍快速选择算法。本题的算法原理和上一题基本上是一模一样的,此处不再详细分析了。简略分析如下
在这里插入图片描述

细节问题:

根据算法原理可知,快速选择完之后,我们并没有把数组排序,只是把最小的k个数扔到了数组前面,数组还是无序的

代码实现:

class Solution 
{
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) 
    {
        srand(time(NULL));
        qsort(stock, 0, stock.size()-1, cnt);

        return {stock.begin(), stock.begin() + cnt};
    }

    void qsort(vector<int>& nums, int l, int r, int k)
    {
        if(l >= r) return;

        // 在数组里找随机值做key
        int key = getRandom(nums, l, r);

        // 数组分三块
        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[--right], nums[i]);
        }

        // 分情况讨论
        // [l, left] [left+1, right-1] [right, r]
        int a = left - l + 1, b = right - left -1;
        if(a > k) qsort(nums, l, left, k);
        else if(a+b >= k) return;
        else qsort(nums, right, r, k-a-b);
    }

    int getRandom(vector<int>& nums, int left, int right)
    {
        return nums[rand() % (right - left + 1) + left];
    }
};

912.排序数组-归并排序

算法原理:

归并排序的大致过程
先取中间点把数组分为两个区间,要把数组排有序,只要左区间有序,右区间有序了,数组就有序了。所以再递归左区间,取中间点把左区间分又为左右两个区间…一直递归,直到左右区间只剩一个元素不可再分割了,这一层进行回退归并过程,归并的核心就是合并两个有序数组,一直归并到第一层,再进行递归右区间…
图解如下:
在这里插入图片描述

细节问题:

这里执行归并操作合并两个有序数组时需要创建临时数组,有两种创建方式:
(1) 边递归边创建
在这里插入图片描述
(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;

        // 找中间点
        int mid = (right + left ) / 2;
        //int mid = (left + right) >> 1;

        // 把左右区间排序
        // [left, mid] [mid+1, right]
        mergeSort(nums, left, mid);
        mergeSort(nums, mid+1, right);

        // 合并两个有序数组
        int cur1 = left, cur2 = mid+1, 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];
    }
};

LCR170.数组中的逆序对

在这里插入图片描述
在这里插入图片描述

算法原理:

这道题比较难。在使用归并分治思想解决这个问题前,先来搞定几个铺垫知识:
(1) 总对数 = 左半区间逆序对个数a + 右半区间逆序对个数b + 左选一个右选一个组成的逆序对个数c
再对第一个知识进行延伸:
(2) 在左半区间找出逆序对个数a后,进行排序,右半区间找出逆序对个数b后,也进行排序,最后再左选一个右选一个组成的逆序对个数c,也跟着排序,此时 a + b + c = 总对数

有了上面两点铺垫知识,就可以引出归并排序的算法了:
把整个数组按中点分成两部分,可以在递归中完成左右两区间逆序对个数的计算,同时进行排序,核心过程是如何计算左选一个右选一个组成的逆序对个数,加排序?如果数组有序,可以统计出一大堆

策略1:用升序,找到该数之前,有多少个数比我大。盯着 cur2 看。
此时是在归并过程中,已经定义了 cur1 和 cur2,分情况讨论:
(1) nums[cur1] <= nums[cur2] -> 此时不能确定左边有多少个数比 nums[cur2]大,cur1++
(2) nums[cur1] > nums[cur2] -> ret += (mid - cur1 + 1) 个对,一次统计出来一堆,再 cur2++
在这里插入图片描述

拓展内容:

策略1中,能否用降序,找到该数之前,有多少个数比我大。也盯着 cur2 看? 不可行
原因:此时在归并过程中,[left, cur1-1] 区间的数都比 nums[cur1] 要大,[mid+1, cur2-1] 区间的数都比 nums[cur2] 要大,如果我们计算 cur1-1 - left +1 的个数,那在 cur1++ 后又要重新计算前面的个数了
在这里插入图片描述

策略2 :用降序,找到该数之后,有多少个数比我小。盯着 cur1 看
(1) nums[cur1] <= nums[cur2] -> 此时不能确定左边有多少个数比nums[cur2]小,cur2++
(2) nums[cur1] > nums[cur2] -> ret += (right - cur2 + 1)个对,一次统计出来一堆,再 cur1++
在这里插入图片描述

代码实现:
这里用的是策略1的升序。

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;

        int ret = 0;
        // 计算中点
        int mid = (left + right) >> 1;

        // 左边的个数+排序  右边的个数+排序
        // [left, mid] [mid+1, right]
        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 j = left; j <= right; j++)
            nums[j] = tmp[j-left];

        return ret;
    }
};

策略1和策略2的代码差异:
策略1:升序

在这里插入图片描述

策略2:降序

在这里插入图片描述

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

在这里插入图片描述
在这里插入图片描述

算法原理:

这题的本质和上一题一样也是计算逆序对的个数,所以也是使用归并分治的思想
因为这道题是求右侧小于当前元素的个数,所以用的是上一题的策略2降序
在这里插入图片描述

但是这道题与上一题不同的是
我们统计出个数之后,不是直接 ret+= 返回,而是要把个数存入另一个数组的和这个元素对应(原始下标)的位置上
所以这里我们还要解决一个问题就是:
当统计出 nums[cur1] 的后面有多少个元素比它小之后,还要能找到这个元素的原始下标(在递归过程中cur1是会移动的)
解决方法:
搞一个与原数组nums同规模的 index 数组,里面的值存的是原数组中每个元素的下标。然后不管nums数组里的元素怎么移动,index 数组里面的值都与它绑定一起移动
在这里插入图片描述

代码实现:

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) >> 1;
        // [left, mid] [mid+1, right]

        // 左右区间的个数
        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];
        }
    }
};

493.翻转对

在这里插入图片描述
在这里插入图片描述
算法原理:

这道题是个逆序对的变式题,但是它不能和 [LCR170.数组中的逆序对] 一样在归并过程中统计翻转对的个数。因为在那道题中的 nums[i] > nums[j] 与归并过程比较时(合并两个有序数组)是一样的,但是这道题的比较是 nums[i] > 2 * nums[j],与归并过程比较时不同

解决方法就是
要在归并过程之前计算翻转对的个数。因为我们要利用这两个数组有序的特性
策略1:计算当前元素后面,有多少元素的两倍比我小,此时降序
此时让 cur1 和 cur2 指向两个区间的开始,盯着 cur1 的元素,先固定cur1不动
(1) 若 nums[cur1] <= 2 * nums[cur2],由于是降序数组,只有 cur2向后移时,才能让nums[cur1] > 2 * nums[cur2]
(2) cur2++,直到 nums[cur1] > 2 * nums[cur2] ,此时 ret += right - cur2 + 1
(3) 再让cur1++,注意此时 cur2 还是一直往后走
(4) 直到 cur1 或 cur2 走出区间
在这里插入图片描述
策略2:计算当前元素之前,有多少元素的一半比我大,此时升序
在这里插入图片描述

代码实现:

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 mid = (left + right) >> 1;
        // [left, mid] [mid+1, right]

        int ret = 0;
        // 计算左右区间的个数
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid+1, right);

        // 计算一左一右的个数
        int cur1 = left, cur2 = mid+1, i = left;
        while(cur1 <= mid)
        {
            while(cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;
            if(cur2 > right) break;
            ret += right - cur2 + 1;
            cur1++;
        }

        // 合并两个有序数组
        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];

        return ret;
    }
};

策略1和策略2的代码差异:
策略1:降序

在这里插入图片描述
在这里插入图片描述

策略2:升序

在这里插入图片描述
在这里插入图片描述

三,算法总结

上面的若干道题都是基于快排和归并的思想解决的,所以最重要的还是要理解这两种排序算法。
如果想要更加详细的学习两种排序算法,请点击下面两篇文章:
(1) 归并排序和计数排序
(2) 快速排序和冒泡排序


原文地址:https://blog.csdn.net/2301_77900444/article/details/141604477

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!