1 数组中的第K个最大元素

1.1 题目解析

1.2 解法

1.3 代码实现

2. 库存管理III

2.1 题目解析

2.2 解法

2.3 代码实现

1 数组中的第K个最大元素

215. 数组中的第K个最大元素 - 力扣（LeetCode）

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

1.1 题目解析

题目本质

这是一个 选择问题：在一堆数里，不用全排好顺序，只要找到 第 k 大的那个值。

我们用三路分区把数分成 < key | == key | > key 三块。
统计“右边比 key 大的个数 c”。
- 如果 k ≤ c：目标还在右边（更大的区间）。
- 如果 c < k ≤ c+b：目标就在“等于区间” ⇒ 直接返回 key。
- 如果 k > c+b：说明第 k 大在左边（更小区间），这时要去左边继续找，并把 k -= (c+b)。
- 停下条件是：k 落在等于区间，结果就是 key。

常规解法
先排序（升序/降序）再取第 n-k / 第 k-1。

问题分析
完整排序复杂度期望 O(n log n)，不满足题设“期望 O(n)”。

思路转折
要 O(n) → 只能做快选（QuickSelect）：

反复三路分区：把区间按 key 切为 <key | ==key | >key；
**找“第 k 大”**时，优先看“右段 >key 的元素个数 c”：
- 若 k ≤ c → 在右段继续；
- 若 k ≤ c + b（b 为等于段个数）→ 直接返回 key；
- 否则 → 去左段，并把 k -= (c + b)（因为这 c+b 个更大的已经被排除在前面）。

1.2 解法

算法思想

三路分区 + 定位“第 k 大”。设

b = right - left - 1（等于段大小），
c = r - right + 1（大于段大小）。
决策：
k ≤ c → 右段；
k ≤ c + b → 返回 key；
否则 → 左段，k = k - (c + b)。

为什么要 k -= (c + b)？

因为递到左段时，前 c + b 个“更大或相等”的元素已经占据了前面的排名，左段内部要找的目标排名相应向前平移。

i）在 [l..r] 内随机取枢轴 key。

ii）三路分区得到三段的边界与大小 b,c。

iii）依据 k 与 c,c+b 的比较，缩小到对应子区间；如进左段要更新 k。

iiii）当命中等于段（k ≤ c + b 且 k > c），返回 key。

易错点 / 踩坑点

while (i < right)；在 >key 分支交换到 --right 时不要移动 i。
段大小别算错：b = right - left - 1，c = r - right + 1。
递左段要 k -= (c + b)；忘了减会错位。
随机下标要含右端点：nextInt(l, r + 1)；
缺少递归基判断(l == r) 会引发 bound must be positive。

1.3 代码实现

import java.util.concurrent.ThreadLocalRandom;class Solution {public int findKthLargest(int[] nums, int k) {return qselect(nums, 0, nums.length - 1, k);}// 三路快选：找第 k 大（k 从 1 开始）private static int qselect(int[] nums, int l, int r, int k) {if (l == r) return nums[l];int left = l - 1, right = r + 1, i = l;int key = nums[ThreadLocalRandom.current().nextInt(l, r + 1)];// 三路分区：<key | ==key | >keywhile (i < right) {if (nums[i] < key) {swap(nums, ++left, i++);} else if (nums[i] > key) {swap(nums, --right, i); // i 不动} else {i++;}}// [l, left] < key; [left+1, right-1] == key; [right, r] > keyint b = right - left - 1;   // 等于段int c = r - right + 1;      // 大于段（更大）if (k <= c) {return qselect(nums, right, r, k);            // 在 >key 段} else if (k <= c + b) {return key;                                    // 落在 ==key 段} else {return qselect(nums, l, left, k - (c + b));    // 去 <key 段}}private static void swap(int[] a, int x, int y) {int t = a[x]; a[x] = a[y]; a[y] = t;}
}

复杂度分析

时间：期望 O(N)（随机枢轴，几何级缩小）。
空间：O(1) 额外空间

2. 库存管理III

LCR 159. 库存管理 III - 力扣（LeetCode）

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

2.1 题目解析

题目本质

这是一个 集合选择问题：不要求有序，只要找出 全局最小的 cnt 个元素。

用三路分区分成 < key | == key | > key。
统计左边 < key 的个数 a、等于区间的个数 b。
- 如果 a ≥ k：目标全在左边，继续递归左段。
- 如果 a < k ≤ a+b：说明“左边+等于区间”已经覆盖住前 k 个 ⇒ 可以停。
- 如果 a+b < k：说明左边和等于区间还不够 k 个，必须把它们都要了，然后去右边继续找剩余 k - (a+b) 个。
- 停下条件是：最终需要的前 k 个都落在“小于等于区间”里。这时数组前缀 [0..k-1] 就是结果，虽然内部无序，但保证集合正确。

常规解法
整体排序后取前 cnt；或用堆（大根堆容量 cnt）。

问题分析

排序：O(n log n) 不必要地重排全部。
大根堆：O(n log cnt)，当 cnt 接近 n 会偏慢。

思路转折
用三路快选（选择）把“前缀”变成全局最小的 cnt 个（内部可无序）：

三路分区得到 <key(a) | ==key(b) | >key；
判断是否已经“覆盖”前缀：当 a + b ≥ cntNeed 时即可停；
若 a ≥ cntNeed → 递左段；
若 a + b < cntNeed → 递右段并 cntNeed -= (a + b)。

2.2 解法

算法思想

在 [l..r] 内反复三路分区，每次决定“继续左/右”或“停”。停下时，数组前缀（全局）即为所需的 cnt 个最小元素（无序）。

i）若 cnt ≤ 0 返回空；若 cnt ≥ n 直接返回拷贝。

ii）l=0, r=n-1, k = cnt（表示“还需收集”的个数）。

iii）三路分区，求 a,b：

a ≥ k → 递左段 [l, left]；
a + b ≥ k → 停（覆盖前缀）；
否则 → 递右段 [right, r]，k -= (a + b)。

iiii）退出后拷贝前 cnt 个；若需要升序，再对前缀排序。

易错点 / 踩坑点

停条件：本题要“集合”，正确停在 a + b ≥ k。
- 仅 a ≥ k 时不要直接停，要继续递左段，否则可能错拿左段里较大的元素。
进入右段时别忘了：k -= (a + b)。
while (i < right) + >key 分支 不移动 i。
无需完整排序，退出后直接拷贝前 cnt 即可。

2.3 代码实现

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;class Solution {public int[] inventoryManagement(int[] stock, int cnt) {int n = stock.length;if (cnt <= 0) return new int[0];if (cnt >= n) return Arrays.copyOf(stock, n);int l = 0, r = n - 1;int k = cnt; // 还需要的数量while (l <= r) {int left = l - 1, right = r + 1, i = l;int key = stock[ThreadLocalRandom.current().nextInt(l, r + 1)];while (i < right) {if (stock[i] < key) {swap(stock, ++left, i++);} else if (stock[i] > key) {swap(stock, --right, i); // i 不动} else {i++;}}// [l, left] < key; [left+1, right-1] == key; [right, r] > keyint a = left - l + 1;     // <keyint b = right - left - 1; // ==keyif (a >= k) {r = left;                 // 递左段} else if (a + b >= k) {break;                    // 覆盖住了前缀，停} else {k -= (a + b);             // 进入右段继续收集l = right;}}int[] ans = Arrays.copyOf(stock, cnt); // 无序即可// 若需要升序：Arrays.sort(ans);return ans;}private static void swap(int[] a, int x, int y) {int t = a[x]; a[x] = a[y]; a[y] = t;}
}

复杂度分析