算法：分治(快排)题目练习

题目一：颜色分类

题目二：排序数组

题目三：数组中的第k个最大元素

题目四：库存管理III

题目一：颜色分类

给定一个包含红色、白色和蓝色、共 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

解法：三指针

这道题和前面算法的第一题：移动零那一题思想类似，移动零是将数组分为两部分，缺点是如果遇到重复元素效率就很低了，而这里是将一个数组分为三部分，是三个指针最终将整个数组划分为满足题意的3部分，完美解决了出现重复元素的情况(i 直接++即可)：

首先定义三个指针，分别是：left、right、i
用 i 来扫描整个区域，left 下标所指向的元素是0这个区域的最右侧，right 是2这个区域的最左侧

当 i 遍历结束时，left和right指针停的位置，就可以将数组分为三部分，但是在遍历过程中，三个指针可以将整个数组分为以下4部分，由left和right代表的含义就可以很清楚的划分：

[0, left]：全为0
[left+1, i-1]：全为1
[i, right-1]：待扫描
[right, n-1]：全为2

所以根据上述的4个区域，将下面讨论 i 遍历数组时可能出现的情况：

nums[i] == 0：swap[++left, i++]
nums[i] == 1：i++;
nums[i] == 2：swap[--right, i]

nums[i] == 0时，先++left，再交换 i 与 left 指向的元素，再i++，优化为swap[++left, i++]
nums[i] == 1时，不用做其他操作，直接i++
nums[i] == 2时，right先--，再与 i 交换，此时 i 指向的元素是right从右边交换过来的，是未扫描的元素，所以 i 不需要++，继续循环判断即可

并且整个循环结束的条件是 i < right，而不是 i < n，因为 right 表示的是2这个区域的最左侧，所以当 i 遇到 right 时，就表示已经遍历完这个数组了

left，right，i初始位置如下图所示：

代码如下：

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

题目二：排序数组

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

示例 1：

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

示例 2：

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

解法：快排(数组分三块的思想)

之前学习的快排是找一个基准值key，将数组分为2部分，再在其中一部分再找一个基准值key1，继续分为2部分，以此类推，如下所示：

这种方式如果在数组全是重复元素的情况下，就会退化成O(N^2)，因为每次都取的最右侧的元素

这道题采用数组分三块的思想，实现快排：

这种方式能够解决出现重复数据时效率很低的问题，因为如果都是重复数据，key的取值就是该元素，排序完一次后，数组中都是=key的区域，而这种方式中我们需要排的是 <key 和 >key 的区域，但是这种情况下没有这两个区域，所以排序结束，仅仅排序了一次，所以如果都是重复数据的时间复杂度是O(N)

分为三部分，左边全是小于key，右边全是大于key，剩余的中间区域就不需要管了，因为左边和右边都划分好了，中间也就划分好了

同样定义三个指针，left、right、i

i来扫描这个数组，left表示小于key的最左侧，right表示大于key的最右侧

所以在扫描数组时分为三步：

nums[i] < key：swap[++left, i++]
nums[i] == key：i++
nums[i] > key：swap[--right, i]

这三步与上一题一模一样，就不细说了

此题还有一个步骤，就是选择key值，之前学过取最左侧的数、取最右侧的数、三数取中等方式，这里采用优化的方式：用随机的方式选择基准的元素

先使用srand种一个随机数种子，再随机得到一个随机数r，使用r%(right - left + 1) + left，得到一个随机数，r就是我们所找的基准值key

代码如下：

class Solution 
{
public:
    vector<int> sortArray(vector<int>& nums) 
    {
        srand(time(nullptr));//生成随机数种子
        qsort(nums, 0, nums.size()-1);
        return nums;
    }
    //数组分三块思想的快排
    void qsort(vector<int>& nums, int l, int r)
    {
        if(l >= r) return;

        int n = nums.size();
        int left = l - 1, right = r + 1, i = l;//数组分三块
        int key = getRandom(nums, l ,r);
        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]三部分
        //只需要继续划分[l, left]和[right, r]这两部分即可，因为中间部分就是==key的
        qsort(nums, l, left);
        qsort(nums, right, r);
    }
    //用随机的方式选择基准的元素
    int getRandom(vector<int>& nums, int left, int right)
    {
        int r = rand(); //得到一个随机数r
        return nums[r % (right - left + 1) + left];
    }
};

题目三：数组中的第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

求数组中的第 k 哥最大元素，也就是俗称的topK问题

topK问题有四类，分别是：第k大、第k小、前k大、前k小，要解决topK问题，一般有两种方法，堆排序(O(N*logN))或是基于快排的快速选择算法(O(N))

如果规定了必须使用时间复杂度为O(N)的算法，那就只能使用快排，否则也可以使用堆排序解决

下面具体说说快排是怎么解决这个题目的：

优化的快排将数组分为3部分，基准元素是key，三部分分别是 < key，== key，> key，由于求的是第k大的元素，那么每次判断只需要判定这个元素会落到哪一部分，就能够排除其他两部分，从而效率非常高

假设 < key，== key，> key 这三部分分别有a、b、c个元素，所以下面根据元素个数分情况讨论，从右侧区域开始判断，因为右侧区域是大元素的集合

①：c >= k，说明第k大就在这个 > key 的区域里，此时取[right, r]区域中找第 k 大的元素即可
②：b + c >= k，说明第k大的元素在== key的区域中，此时就不需要比较了，直接返回key即可，因为这个区域的数大小都是key
③：走到这里，说明①②都不成立，所以需要去[l, left]区域找第 k - b -c 大的元素

此题的解决方式就是在上一题的快排的基础上实现的

代码如下：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(nullptr));
        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);
        // 根据基准元素将数组分为3块
        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);//注意不是k，而是k-b-c
    }

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

题目四：库存管理III

仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。

示例 1：

输入：stock = [2,5,7,4], cnt = 1
输出：[2]

示例 2：

输入：stock = [0,2,3,6], cnt = 2
输出：[0,2] 或 [2,0]

这道题，观察给出的题目信息，其实也是一个topK问题，只不过这里的topK问题是求前k个最小的数

此题有很多解法，例如：

解法一：排序，最后取出前k个最小的数，时间复杂度O(NlogN)

解法二：堆排序，时间复杂度O(Nlogk)

解法三：快速选择算法，时间复杂度O(N)

这里只实现快速选择算法，前两种都比较简单

依然是随机选择基准元素 + 把数组分三块的思想，依旧是分为三部分,分别是 < key，== key，> key，这三部分分别有a、b、c个元素，并且left指向的是最左侧区域的最后一个值，right表示最右侧区域的第一个值，如下所示：

因为此题求的是前k小的元素，所以先考虑 < key 的这个区域，步骤如下：

①：a > k，说明就在< key 的这个区域，在[l, left]区域中查找
②：a + b >= k，直接返回
③：走到这说明①②都不满足，所以在 >key 这个区域即[right, r]中，找k - a - b 个最小元素即可

代码如下：

class Solution 
{
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) 
    {
        srand(time(nullptr));
        qsort(stock, 0, stock.size()-1, cnt);
        //最后将前k个元素返回即可
        return {stock.begin(), stock.begin() + cnt};
    }

    void qsort(vector<int>& nums, int l, int r, int k)
    {
        if(l >= r) return;
        //随机选择一个基准元素
        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 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];
    }
};

分治中，关于快排的题目到此结束