目錄

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

復雜度分析

• 時間：期望 O(n)；

• 空間：O(1) 額外空間。