算法实战：数组中第 K 个最大元素与最小的 K 个数

流程解析

46. 最小的 K 个数

题目链接

LCR 159. 库存管理 III - LeetCode

题目描述

仓库管理员以数组 stock 形式记录商品库存表。stock[i] 表示对应商品编号。请返回所有编号小于等于 cnt 的商品编号。

题目示例

解法：快速选择算法

核心思路

这道题与上一题逻辑相似，只是方向相反。我们要找最小的 k 个数，因此需要关注左侧的小数区域。同样采用三路划分策略，将小于基准的元素移到左侧，统计左侧区域数量即可定位目标区间。

相比全排序（O(NlogN)）和堆排序（O(NlogK)），快速选择在平均情况下时间复杂度接近 O(N)，效率更高。

C++ 代码实现

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        if (cnt == 0) {
            return {};
        }
        srand(time(NULL));
        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++;
            }
        }
        
        // 左侧区域（小于 key）元素个数 >= cnt，说明目标在左侧
        if (l - left + 1 >= cnt) {
            return Top_k(nums, left, l, cnt);
        }
        // 左侧加中间区域 >= cnt，说明目标已包含在左侧及中间，无需再分
        else if (r - left >= cnt) {
            return;
        }
        // 否则目标在右侧，需调整 cnt
        else {
            return Top_k(nums, r, right, cnt - (r - left));
        }
    }
};

流程解析