分治算法：快速排序及经典题目解析

44. 颜色分类

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

即对这三类元素进行排序。

解法：三指针

• i 指针遍历数组
• left 指针标记 0 区域最右侧
• right 标记 2 区域的最左侧

此时数组被划分为四个部分：

• [0, left]：全是 0
• [left+1, i-1]：全都是 1
• [i, right-1]：待扫描的元素
• [right, n-1]：全都是 2

逻辑如下：

1. 如果 nums[i] == 0：将当前位置与 nums[++left] 交换，然后 i++。这样先将 left 右移再交换，确保 left 指向 0 区域的边界。
2. 如果 nums[i] == 1：直接 i++，因为中间区域存放的是 1。
3. 如果 nums[i] == 2：将当前位置与 nums[--right] 交换。注意此时不移动 i，因为从右侧交换过来的元素尚未扫描。

当 i 和 right 相遇后，扫描完成。

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        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]);
        }
    }
};

45. 快速排序

题目链接 给你一个整数数组 nums，请你将该数组升序排列。 你必须在不使用任何内置函数的情况下解决问题，时间复杂度为 O(n log 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]

利用数组分三块的思想实现快排：左边小于 key，中间等于 key，右边大于 key。

优化：随机基准元素

使用随机方式选择基准元素，使时间复杂度接近 O(n log n)。 随机下标生成公式：r % (right - left + 1) + left

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

原理

选择一个基准元素（pivot），将数组划分为两部分，使得左边部分的所有元素都小于等于基准元素，右边部分的所有元素都大于等于基准元素。递归地对左右两部分子数组分别进行快速排序。由于分解过程中元素已被放置在正确的相对位置上，因此不需要额外的合并操作。

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

题目链接 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

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

解法：快速选择算法

基于快排的分治思想。数组分三块 + 随机选择基准元素。 如果第 k 大落在了大于 key 的区间上，则左边区间不用找。

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; // 右区间元素个数
        int b = right - 1 - (left + 1) + 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];
    }
};

• c >= k: 说明第 k 个最大的元素位于右区间，递归查找右区间。
• b + c >= k: 说明第 k 个最大的元素位于中间区间，直接返回 key。
• else: 说明位于左区间，递归查找左区间，调整 k。

47. 最小的 k 个数

题目链接 输入整数数组 arr，找出其中最小的 k 个数。可以不按照从小到大的顺序返回。

示例 1： 输入：arr = [3,2,1], k = 2 输出：[1,2] 或 [2,1]

示例 2： 输入：arr = [0,1,2,1], k = 1 输出：[0]

解法：快速选择算法 O(N)

随机选择基准元素 + 数组分成三块。

class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> nums, int k) {
        srand(time(NULL));
        qsort(nums, 0, nums.size() - 1, k);
        return {nums.begin(), nums.begin() + k};
    }

    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;
        int 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 l, int r) {
        return nums[rand() % (r - l + 1) + l];
    }
};

• a > k: 前 k 个最小元素都在小于基准值的部分，递归左侧。
• a + b > k: 前 k 个最小数已在左侧或中间找到，结束。
• else: 需递归处理右侧，寻找剩余 k - a - b 个最小数。