算法沉淀——分治算法（leetcode真题剖析）-快排思想

时间：2024-02-15 22:43:22

01.颜色分类

题目链接：https://leetcode.cn/problems/sort-colors/

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

思路

具体的思路可以分为以下三个部分：

  1. 红色部分（0）： 通过交换，保证红色元素的右边界 left 的左侧都是红色元素。初始时，left 设置为-1。
  2. 白色部分（1）： 遍历过程中，遇到白色元素（1）时，直接将指针 i 向右移动，不进行交换。白色元素已经排列在红色元素的右侧，所以不需要额外操作。
  3. 蓝色部分（2）： 通过交换，保证蓝色元素的左边界 right 的右侧都是蓝色元素。初始时，right 设置为数组的长度。

整个过程在遍历指针 i 小于右边界 right 的情况下进行。当 i 与 right 相遇时，排序完成。

代码

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

02.排序数组

题目链接：https://leetcode.cn/problems/sort-an-array/

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

提示：

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

思路

普通快排在这里是通过不了的，所以我们可以使用上面颜色分类的思想进行三路划分的优化

三路划分是对传统快速排序算法的一种改进，通过将数组划分为三个部分：小于、等于、大于基准值，从而在存在大量相同元素的情况下，提高了性能。

传统快速排序在处理有大量相同元素的数组时可能会导致不均匀的划分，使得递归树不平衡，进而影响性能。三路划分通过在划分过程中将数组分为小于、等于、大于基准值的三个部分，有效地解决了这一问题，具有以下优势：

  1. 减少重复元素的递归处理： 在存在大量相同元素的情况下，传统快速排序可能导致递归深度较大，而三路划分能够将相同元素聚集在一起，从而减少递归深度。
  2. 避免不必要的交换： 在传统快速排序中，可能会进行多次相同元素的交换，而三路划分通过将相同元素聚集在一起，避免了不必要的交换操作，提高了性能。
  3. 适用于含有大量重复元素的场景： 当数组中存在大量相同元素时，三路划分能够更好地利用重复元素的信息，提高排序效率。

三路划分的核心思想是通过一个循环，将数组划分为小于、等于、大于基准值的三个部分。这样，相同元素被聚集在等于基准值的部分，从而在递归过程中能够更高效地处理重复元素。这一优化使得算法在处理包含大量相同元素的数组时，性能更为稳定。

代码

class Solution {
public:
    int getRandom(vector<int>& nums,int left, int right){
        return nums[rand()%(right-left+1)+left];
    }
    
    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);
    }

    vector<int> sortArray(vector<int>& nums) {
        srand(time(NULL));
        qsort(nums,0,nums.size()-1);
        return nums;
    }
};

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

题目链接：https://leetcode.cn/problems/kth-largest-element-in-an-array/

给定整数数组 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

思路

这里最常规的写法应该是使用堆排，但是这样达不到O(n)的时间复杂度，所以这里我们结合快排中的三路划分思想

代码

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];

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

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

        // 3. 分情况讨论
        int c = r - right + 1, b = right - left - 1;
        if (c >= k) {
            // 第 k 大元素在右侧部分
            return qsort(nums, right, r, k);
        } else if (b + c >= k) {
            // 第 k 大元素等于基准元素
            return key;
        } else {
            // 第 k 大元素在左侧部分
            return qsort(nums, l, left, k - b - c);
        }
    }

    int getRandom(vector<int>& nums, int left, int right) {
        return nums[rand() % (right - left + 1) + left];
    }
};
  1. 计算左、右和基准三个部分的元素个数：
    • c 表示右侧部分元素的个数，即大于基准元素的个数。
    • b 表示基准元素左侧部分元素的个数，即等于基准元素的个数。
  2. 判断第 k 大元素的位置：
    • 如果右侧部分元素个数 c 大于等于 k，说明第 k 大元素在右侧部分。因此，递归地在右侧部分中继续寻找第 k 大元素。
    • 如果 b + c 大于等于 k，说明第 k 大元素等于基准元素。此时，基准元素即为所求的第 k 大元素，直接返回基准元素的值。
    • 如果以上两个条件都不满足，说明第 k 大元素在左侧部分。因此，递归地在左侧部分中继续寻找第 k 大元素，同时将 k 减去右侧和基准元素的个数。

这样的划分和递归过程保证了在不同情况下都能正确地找到第 k 大元素，从而完成整个算法。这是随机化快速排序在选择第 k 大元素时的一种处理策略，通过考虑基准元素左右两侧的元素个数，提高了算法在寻找第 k 大元素时的效率。

04.库存管理 III

题目链接：https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/

仓库管理员以数组 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]

提示：

  • 0 <= cnt <= stock.length <= 10000 0 <= stock[i] <= 10000

思路

这一题和上一题的思路基本一致，同样我们使用快速选择的算法，可以使时间复杂度达到O(n)，只不过需要简单做一些调整

代码

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

        // 随机选择基准元素
        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[--right], nums[i]);
            }
        }

        int a = left - l + 1, b = right - left - 1;

        // 根据划分情况递归处理
        if (a > k) {
            // 第 k 小元素在左侧部分
            qsort(nums, l, left, k);
        } else if (a + b >= k) {
            // 第 k 小元素在基准元素右侧，且可能包含部分基准元素
            return;
        } else {
            // 第 k 小元素在右侧部分
            qsort(nums, right, r, k - a - b);
        }
    }

    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        srand(time(NULL));

        // 调用随机化快速排序
        qsort(stock, 0, stock.size() - 1, cnt);

        // 返回前 cnt 小的商品
        return {stock.begin(), stock.begin() + cnt};
    }
};