【基础算法总结】分治—快排

分治—快排

  • 1.分治
  • 2.颜色分类
  • 3.排序数组
  • 4.数组中的第K个最大元素
  • 5.库存管理 III

在这里插入图片描述

点赞????????收藏????????关注????????
你的支持是对我最大的鼓励,我们一起努力吧!????????

1.分治

分治思想就如同它的名字一样:分而治之

将一个大问题划分成若干个相同或者相识的子问题。然后在将子问题在划分成若干个相同或者相识的子问题,直到划分到不能在划分。然后解决子问题,子问题都解决完了,大问题也就被解决完了。快速排序和归并排序就用的分治思想。

在这里插入图片描述

以前我们学快速排序是在数组中选择一个基准元素,然后将数组分成左右两个区间,左区间比基准元素小,右区间比基准元素大。然后递归的去左区间和有区间排序,这种做法是将数组分成了两份。但是对于重复元素非常多的数组即使使用快速排序也会超时。因此这里我们学习新的划分方法,将数组划分成三份。

还是选一个基准元素将数组划分成三份,左区间元素都比基准元素小。中间区间元素和基准元素相同,右区间元素都比基准元素大。因为中间都是等于key的一定就是在最终位置,所以接下来递归还是只考虑左区间和右区间。

在这里插入图片描述

2.颜色分类

题目链接:75. 颜色分类

题目分析:

在这里插入图片描述
说起来这道题并不是真正的分治快速排序,而是把数组按照一定规则划分成三块的。当把这道题解决后,快排写的就非常简单。

这道题就相当于选择一个基准元素1,把小于1的放左边,大于1的放右边,等于1的放中间。

算法原理:

双指针可以将数组分成两块,具体怎么分,双指针系列第一道题移动零。这里我们需要三个指针将数组分成三块!

每个指针的作用:
i指针:遍历整个数组
left:标记 0 区域的最右侧
right:标记 2 区域的最左侧

在这里插入图片描述

三个指针将数组分成4份:
[0,left] :全都是0
[left+1,i-1]:全都是1
[i,right-1]:待扫描的元素
[rigth+1,n-1]:全都是2

在这里插入图片描述

接下来就讨论nums[i]是0或1或2应该怎么办?

nums[i]为0的时候,要把0加入到左边区域,left指向的是 0 最右侧区域,此时left+1,然后将 i 位置和 left+1 元素交换,然后i+1。

在这里插入图片描述

还有一种极端情况 i 就在 left+1的为位置,并且正好是0。但是这种处理方法和上面一样。

在这里插入图片描述

nums[i]为1的时候,i 指针往后走就行了

在这里插入图片描述

nums[i]为2的时候,我们要将2加入到右边区间,也就是加入到 right - 1 的位置。交换 i 位置和 right -1 位置的元素。但是此时需要注意的是 交换给 i 位置的元素是待扫描的元素,因此 i 指针不能往后走!

在这里插入图片描述

class Solution {
public:
    void sortColors(vector<int>& nums) {

        int n = nums.size();
        int i = 0, left = -1, right = n;
        while(i < right)
        {
            if(nums[i] == 0)
                swap(nums[++left], nums[i++]);
            else if(nums[i] == 2)
                swap(nums[--right], nums[i]);
            else
                ++i;
        }
    
    }
};

3.排序数组

题目链接:912. 排序数组

题目描述:

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

在数组中选择一个基准元素key,根据key将数组分成左右区间,左区间元素小于等于key,右区间元素大于key。这个key就处于排序的最终位置。然后在将左区间排排序,右区间排排序,重复上述过程。整体就有序了。时间复杂度(nlogn)

但是如果数组都是重复元素,此时选择基准元素间将数组分成左右两区间就不行了。时间复杂度退化成O(n^2)

在这里插入图片描述

所以我们学习一个更优的做法,将 数组分三块 思想来实现快速排序

我们先选一个基准元素key,将数组分成三块。左区间小于key,中间区间等于key,右区间大于key。中间区间已经在排序后的最终位置,所以只用去去左区间排序,右区间排序。重复上述过程,整体就有序了。

数组如何分三块和颜色分类一模一样。定义一个i 指针 扫描数组,left指针 指向左区间小于key的最右侧, right指针 指向右区间大于key的最左侧。然后分情况讨论就好了。

在这里插入图片描述

即使数组全部都是重复元素,我们经过一次数组划分,整个数组都是中间区间,左右区间不存在,也不用在递归下去了,直接结束。时间复杂度O(n)

在这里插入图片描述

优化:用随机的方式选择基准元素
之前常用的三数取中,还是不够随机。要想时间复杂度逼近O(nlogn)就要用随机的方式选择基准元素。

随机选择就是让数组中每个元素被选择的概率相同,然后返回被选择的元素。

使用产生随机数的函数 rand(),让生成的随机数%这个区间的长度,然后加上left,这是在这个区间内的随机数的下标,然后返回对应下标的元素。
在这里插入图片描述

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        srand((unsigned int)time(nullptr));
        QuickSort(nums,0,nums.size()-1);
        return nums;

    }


    void QuickSort(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]);
        }

        QuickSort(nums, l , left);
        QuickSort(nums, right, r);

    }

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

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

题目链接:215. 数组中的第K个最大元素

题目分析:

在这里插入图片描述
给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。其实就是一个TopK问题。

TopK问题四种问法:

第 k 个最大的元素
第 k 个最小的元素
前 k 个最大的元素
前 k 个最小的元素

可以使用堆排序, 时间复杂度O(nlogn)

还有一种就是快速选择算法,快速选择算法是基于快排实现的。时间复杂度O(n)。

算法原理:

一定要把数组分三块+随机选择基准元素掌握,才能懂这道题。

核心操作还是选择一个基准元素key,将数组分成< key , = key ,> key 三块区域。在这道题中我们是要找到第K大元素,这个第K大元素有可能落在三个区域中的任何一个区域。如果有一种方法能够确定第K大元素能够落在那个区域,那另外两个区域就不用考虑了。仅需在确定的区域里面递归找。所以说它是比快排更快的一种算法。
在这里插入图片描述

接下来重点就是如何确定第K大元素落在左边区域、中间区域、还是右边区域。
此时我们先统计出每个区域中元素的个数,假设左边区域元素个数为 a,中间区域元素个数为 b,右边区域元素个数为 c。
在这里插入图片描述

此时就分三种情况讨论:

因为求第K大,所以可以先考虑右边区域,因为右边区域都是大元素聚集地,第K大最有可能在右边区域。

  1. 第一种情况:如果第K大是落在右边区域,此时 c >= K,因为c表示大元素有多少个,而K表示找第K大的元素。如果 c >= K ,那第K大一定是落在右边区域。此时我们仅需到[right,r],找第K大
  2. 第二种情况:如果到了第二情况那第一种情况一定是不成立的。如果第K大是落在中间区域,此时 b + c >= K,又因为第一种情况不满足,所有第K大一定是落在中间区域。此时就找到了也不用递归了。直接返回就可以
  3. 第三种情况:第一、第二种情况全部不成立,第K大一定落在左边区域,去**[l,left]找**,但是此时并不是去找第K大了,本来是想在整个区间找第K大,但是第K大元素确定不在中间区域和右边区域,中间和右边区域都要被抛弃,此时去找左边区间找的是第 K - b - c 大的元素

在这里插入图片描述

class Solution {
public:

    int findKthLargest(vector<int>& nums, int k) {

        srand((unsigned int)time(nullptr));
        return QuickSort(nums,0,nums.size()-1,k);
    }


    int QuickSort(vector<int>& nums, int l, int r, int k)
    {
    	//不用考虑区间不存在的情况,因为下面的判断K落在那个区域,只要满足进入的一定是有的
        if(l == r) return nums[l];

        // 1.随机选择基准元素
        int key = GetRandom(nums, l, r);

        // 2.根据基准元素将数组分三块
        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]);
        }

        //3.计算每个区间都有多少元素,然后选择区间递归
        int b = right - 1 - left , c = r - right + 1; 
        if(c >= k) return QuickSort(nums, right, r ,k);
        else if(b + c >= k) return key;
        else return QuickSort(nums, l, left, k - b - c);

    }

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



    // int findKthLargest(vector<int>& nums, int k) {
    //     //前k个建小堆
    //     priority_queue<int,vector<int>,greater<int>> pq(nums.begin(),nums.begin()+k);

    //     //N-k与堆顶元素比较,大于堆顶就入堆,再次调整成小堆
    //     for(size_t i=k;i<nums.size();++i)
    //     {
    //         if(nums[i]>pq.top())
    //         {
    //             pq.pop();
    //             pq.push(nums[i]);
    //         }
    //     }

    //     return pq.top();
     
    // }
};

5.库存管理 III

题目链接:LCR 159. 库存管理 III

题目分析:

在这里插入图片描述

实际上这也是一个TopK问题,让找前K个最小元素。注意返回结果并不考虑顺序问题。

算法原理:

解法一:排序 ,时间复杂度O(nlogn)
解法二:堆 ,时间复杂度O(nlogk)
解法三:快速选择算法,时间复杂度O(n)

数组分三块+随机选择基准元素。
选择一个基准元素key,将数组分成< key , = key ,> key 三块区域。找前K个最小的元素,落在三个区域中任何一个。统计除每个区域元素个数,然后选择去那个区域找。

分三种情况:
因为前K下最小元素最有可能出现在左边区域,因此先判断左边区域

  1. a >= K ,去[l,left] 找前K个最小元素
  2. b + a >= K ,直接返回
  3. 1、2都不成立,去[right,r] 找 K - a - b 个最小元素

在这里插入图片描述

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& nums, int k) {

        srand((unsigned int)time(nullptr));
        QuickSort(nums, 0, nums.size() - 1, k);
        return {nums.begin(),nums.begin() + k};
    }

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

        // 1. 随机选择基准元素
        int key = GetRandom(nums, l, r);
        // 2. 数组分三块
        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]);
        }

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

    int GetRandom(vector<int>& nums, int left, int right)
    {
        return nums[rand() % (right - left + 1) + left];
    }
};
上一篇:MySQL与Oracle 执行计划对比


下一篇:MySQL Server时区支持