快速选择算法实战：第 K 大元素与最小 K 个数

46. 最小的 K 个数

题目描述

输入整数数组 stock 和整数 cnt，找出数组中最小的 cnt 个数。

解法：快速选择算法

思路解析

这道题与上一题类似，但目标是找到最小的 k 个数。我们依然可以使用快速选择的分区思想。

不同的是，这里不需要返回具体的某个值，而是需要将数组前 cnt 个位置调整为最小的 cnt 个数。同样采用三路划分策略，根据区间长度判断目标范围是否在当前区间内。如果左侧区间长度足够容纳 cnt 个数，则继续在左侧查找；否则，如果包含中间区域，则说明已经找到了所有需要的数，无需再操作；否则需要在右侧继续查找并更新 cnt。

相比堆排序 O(NlogK) 或全排序 O(NlogN)，此方法在数据量较大时效率更高，平均时间复杂度接近 O(N)。

C++ 代码实现

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        if (cnt == 0) {
            return {};
        }
        srand(time(NULL));
        // 调用快速选择函数，将最小的 cnt 个数调整到数组前部
        Top_k(stock, 0, stock.size() - 1, cnt);
        return vector<int>(stock.begin(), stock.begin() + cnt);
    }

    void Top_k(vector<int>& nums, int left, int right, int cnt) {
        if (left == right) {
            return;
        }
        
        int key = nums[rand() % (right - left + 1) + left];
        int l = left - 1, r = right + 1, i = left;
        
        while (i < r) {
            if (nums[i] > key) {
                swap(nums[i], nums[--r]);
            } else if (nums[i] < key) {
                swap(nums[i++], nums[++l]);
            } else {
                i++;
            }
        }
        
        // 左侧区间长度 >= cnt，说明最小的数都在左侧
        if (l - left + 1 >= cnt) {
            return Top_k(nums, left, l, cnt);
        }
        // 左侧 + 中间区间长度 >= cnt，说明已经包含了所有需要的数
        else if (r - left >= cnt) {
            return;
        }
        // 否则在右侧继续查找
        else {
            return Top_k(nums, r, right, cnt - (r - left));
        }
    }
};

执行流程总结

这两道题的核心都在于快速选择（Quick Select）。通过随机基准值和三路划分，我们避免了不必要的完全排序。在实际运行中，这种分治策略能显著减少比较次数，特别是在处理大规模数据时，性能优势非常明显。