題目與適用情境
給定整數陣列 nums 和整數 k，回傳依排序位置計算的第 k 大元素，而非第 k 個不同元素。假設 1 <= k <= nums.length <= 100,000，且 -10,000 <= nums[i] <= 10,000。
例如，nums = [3, 2, 1, 5, 6, 4]、k = 2 時回傳 5。對 nums = [3, 2, 3, 1, 2, 4, 5, 5, 6]、k = 4，答案是 4：相同數值會占據多個排序位置。
這是具代表性的順序統計量演算法題。完整排序、大小為 k 的最小堆積和快速選擇在不同限制下都成立。本文主解法使用隨機化三向快速選擇，因為輸入是記憶體中的可變陣列，而且只查詢一個排名。實作會修改 nums；若呼叫端要求保留原陣列，應先複製並計入額外空間。
面試官在評估什麼
第一個訊號是能否說清楚契約。「第 k 大」代表降冪排序中的第 k 個位置，重複值也要計數。它不代表第 k 個不同值、最大的 k 個值，也不代表零起算陣列中的索引 k。轉成升冪後，目標的零起算索引是 n - k。
第二個訊號是能否推導不同方案，而非直接背快速選擇。排序是 O(n log n) 的穩妥基線；大小為 k 的最小堆積用 O(n log k) 時間與 O(k) 空間，也適合串流輸入；快速選擇捨棄不可能包含目標的分割區，期望時間為 O(n)，但隨機化樞紐不會消除 O(n^2) 最差情況。
第三個訊號是能否明確說出分割不變量。程式碼「看起來像快速排序」並不足夠。候選人應說明 lt 之前、lt 到 i、i 到 gt、gt 之後各自已知什麼，並解釋縮小後的區間為何仍包含目標排名。
最後還會評估重複值、輸入修改契約、無效輸入行為、用迭代避免遞迴深度風險，以及能否用簡單正確的基準答案做對照測試。只有最佳化程式碼，沒有證明邊界和對抗測試，答案仍不完整。
回答前應釐清的問題
- 第 k 大是否計算重複值？ 本文依排序位置計算，因此
[5, 5, 4]的第 2 大是5。若要求不同值排名，就需要去重或依頻率選擇。 k是否保證有效，陣列能否為空？ 題設保證1 <= k <= n。獨立實作仍會對越界參數拋出ValueError，讓契約明確。- 可以修改輸入陣列嗎？ 原地分割只需
O(1)輔助空間。禁止修改時先複製，額外空間變為O(n)。 - 輸入完整存在，還是持續到達？ 快速選擇需要隨機存取和修改；無界串流更適合大小為
k的最小堆積。 - 只查詢一次，還是對同一資料查詢多個排名？ 單次查詢適合快速選擇；後續查詢很多時，一次排序的
O(n log n)成本可能更划算。 - 數值範圍是否真的小且固定？ 題設只有 20,001 個可能整數，因此計數法可用
O(n + R)時間、O(R)空間解決，R是值域寬度；數值無界時不能把它當通用方案。 - 是否必須保證最差時間？ 隨機化快速選擇是期望線性時間。若要求確定性最差線性時間，應討論中位數的中位數；也可選擇較易實作、時間可預測的
O(n log k)堆積方案。
30 秒回答框架
「重複值依排序位置計數，所以第 k 大對應升冪索引 n - k。排序是簡單的 O(n log n) 基線；大小為 k 的最小堆積適合串流或不可修改輸入，時間為 O(n log k)。本題只查一個排名且陣列可修改，我會用迭代的隨機化快速選擇。每輪依隨機樞紐分成小於、等於和大於三段；n - k 落在等值段就回傳樞紐，否則只保留包含目標索引的一側。三向分割能讓重複值很多的輸入一次跳過整個等值段。期望時間 O(n)，最差 O(n^2)，輔助空間 O(1)。我會用排序結果作為 oracle，驗證全相等、已排序、反向排序、重複值密集、邊界 k 和隨機陣列。」
逐步深入解答
先建立基準答案。升冪排序後回傳 sorted(nums)[len(nums) - k]，最容易解釋，也能確認排名換算。若為了保留原陣列而複製，複雜度是 O(n log n) 時間與 O(n) 空間。它也能作為後續隨機測試的正確性 oracle。
當 k 較小或資料逐筆到達時，固定大小堆積更合適。把每個值壓入最小堆積；大小超過 k 時移除最小值。處理結束後，堆頂是最大 k 個值中最小的一個，也就是第 k 大。堆積最多保存 k 個值，因此時間為 O(n log k)、空間為 O(k)。若 k 接近 n 且完整陣列已在記憶體中，這個優勢會縮小。
快速選擇利用「只關心一個最終位置」這一點。先把降冪排名換成 target = len(nums) - k。每輪在活動區間 [left, right] 隨機選擇樞紐值，並做荷蘭國旗式三向分割。掃描期間維持：
[left, lt)全部小於樞紐。[lt, i)全部等於樞紐。[i, gt]尚未分類。(gt, right]全部大於樞紐。
掃描完成後，[lt, gt] 是完整等值段。若 target < lt，繼續搜尋較小值一側；若 target > gt，繼續搜尋較大值一側；否則目標位於等值段，樞紐就是答案。對 [7, 7, 7, 7] 這類輸入，普通二向分割可能反覆移除極少元素，三向分割一次掃描即可回傳。
import random
def find_kth_largest(nums: list[int], k: int) -> int:
if not 1 <= k <= len(nums):
raise ValueError("k must be between 1 and len(nums)")
target = len(nums) - k
left = 0
right = len(nums) - 1
while left <= right:
pivot = nums[random.randrange(left, right + 1)]
lt = left
i = left
gt = right
while i <= gt:
if nums[i] < pivot:
nums[lt], nums[i] = nums[i], nums[lt]
lt += 1
i += 1
elif nums[i] > pivot:
nums[i], nums[gt] = nums[gt], nums[i]
gt -= 1
else:
i += 1
if target < lt:
right = lt - 1
elif target > gt:
left = gt + 1
else:
return pivot
raise RuntimeError("unreachable for a valid k")i 的遞增刻意不對稱。大於樞紐的值與 nums[gt] 交換後，新進入 i 的值尚未分類，因此 i 不能移動；小於樞紐的值向左交換後，相關位置的類別都已確定，所以 lt 和 i 同時遞增。
正確性來自不變量和排名排除。分割保留所有輸入元素，並讓小值位於等值段之前、大值位於等值段之後，因此 [lt, gt] 中每個升冪位置的值都等於樞紐。目標在等值段外時，被捨棄的一側和等值段都不可能占據目標索引；保留區間仍包含答案。每輪不是回傳，就是嚴格縮短區間，因此合法目標最終必然被回傳。
每次分割只掃描目前區間一次。隨機樞紐下，連續保留區間的期望總工作量為 O(n)。若連續選到極端樞紐，區間可能依序只有 n - 1、n - 2 個元素，最差時間為 O(n^2)。實作使用迴圈和原地分割，輔助空間為 O(1)；這裡不把輸入陣列和亂數產生器狀態計入輔助儲存。
測試應使用排序 oracle，而非只檢查固定範例：
def oracle(nums: list[int], k: int) -> int:
return sorted(nums)[len(nums) - k]
cases = [
([3, 2, 1, 5, 6, 4], 2),
([3, 2, 3, 1, 2, 4, 5, 5, 6], 4),
([1], 1),
([7, 7, 7, 7], 3),
([-5, -1, -3, -1], 2),
(list(range(1000)), 1),
(list(range(1000)), 1000),
]
for values, rank in cases:
assert find_kth_largest(values.copy(), rank) == oracle(values, rank)再產生大量重複值陣列，對每個合法 k 與 oracle 比較；同時斷言 k = 0、k > n 和空陣列會拋出約定錯誤。固定隨機種子可以重現失敗案例，多組種子則涵蓋不同分割路徑。
高品質示範回答
「我先確認重複值會占據多個排序位置，並假設 k 有效。若陣列升冪排列，答案索引是 n - k。最簡單方案是排序後取值，時間 O(n log n)；串流資料可維護大小為 k 的最小堆積，時間 O(n log k)。
本題只有一次查詢且允許修改陣列，我會用隨機化快速選擇。在目前區間隨機取樞紐，把元素分成小於、等於和大於三段。三向分割很重要，因為重複值應占多個排名，而且全相等輸入應在一次分割後結束。分割完成後，若 n - k 落在等值段就回傳樞紐，否則只保留包含目標索引的一側並迭代。
掃描不變量是：lt 前都較小，lt 到 i 都相等，gt 後都較大，中間仍未分類。這能證明最終等值段對應正確的排序排名區間，保留的一側繼續包含答案。
隨機樞紐下期望時間是 O(n)，最差仍為 O(n^2)；迴圈和原地分割只用 O(1) 輔助空間。我會明確說明函式會修改輸入，並用排序 oracle 對產生的陣列做對照，涵蓋重複值、全相等、已排序、反向排序、負數、k = 1 和 k = n。」
常見錯誤
- 回傳第 k 個不同值 → 契約依排序位置計算重複值 → 直接轉換為升冪索引
n - k，不要去重。 - 在升冪陣列使用索引
k或k - 1→ 排名方向轉換錯誤 → 檢查k = 1應對應n - 1，k = n應對應0。 - 把最小堆積複雜度寫成
O(n log n)→ 堆積始終不超過k個元素 → 寫明O(n log k)時間與O(k)空間。 - 同時遞迴兩個分割區 → 退化為快速排序的工作量 → 只進入包含
target的區間。 - 固定選第一個或最後一個樞紐 → 有序或特製輸入可連續產生大小為
n - 1的區間 → 隨機選擇樞紐，並保留最差情況說明。 - 使用二向分割卻不討論重複值 → 重複值密集時進展很差 → 建立完整等值段，目標落入時立即回傳。
- 與
gt交換後仍遞增i→ 新換入的值尚未分類，會被略過 → 保持i不動直到該值完成分類。 - 宣稱隨機化保證線性時間 → 仍可能連續遇到差樞紐 → 表述為期望
O(n)、最差O(n^2)。 - 不說明會修改輸入 → 呼叫端可能依賴原順序 → 公開修改契約，或複製並計入
O(n)空間。 - 只測兩個範例 → 無法發現排名偏移、重複值與分割錯誤 → 用排序 oracle 涵蓋邊界、結構化和隨機輸入。
追問與應對方式
追問 1：若輸入是無界串流，方案如何變化？
完整的隨機存取陣列不存在，快速選擇不再適用。維護最多 k 個值的最小堆積：未滿時加入，已滿後只在新值較大時替換堆頂。堆頂始終是目前第 k 大。單次更新 O(log k)、查詢 O(1)、空間 O(k)。若 k 也任意改變，現有狀態可能不足，需要更豐富的有序結構或保留原始資料。
追問 2：如果函式必須保留輸入陣列呢？
最直接的方法是複製為 working = nums.copy() 後執行快速選擇，輔助空間變為 O(n)。大小為 k 的堆積只用 O(k) 空間且不修改輸入，k 較小時可能更適合。若 n 不大或後續有多次排名查詢，排序副本通常更簡單。
追問 3：能否保證最差線性時間？
中位數的中位數能選出在最差情況下排除固定比例元素的樞紐，實現確定性 O(n) 選擇。它的實作與常數較大，所以除非題目明確要求最差上界，面試時通常優先隨機化快速選擇。固定大小堆積則提供更容易實作、可預測的 O(n log k) 方案。
追問 4：如何利用題設中的小整數值域？
為 -10,000 到 10,000 建立頻率陣列，掃描輸入計數，再從高到低走訪桶並從 k 扣除頻率；第一個包含剩餘排名的桶就是答案。值域寬度 R = 20,001 時，時間 O(n + R)、空間 O(R)。它是確定性的，也自然處理重複值，但值域很大或無界時不再適合。
追問 5：若要求回傳已排序的最大 k 個元素呢？
輸出目標已不只是單一順序統計量。大小為 k 的堆積最後再排序，時間為 O(n log k + k log k)、空間 O(k)。也可以先快速選擇分出最大的 k 個值，再排序該部分，期望時間 O(n + k log k)。應依是否允許修改、記憶體、最差時間要求與輸出是否必須有序選擇。
追問 6：如何讓隨機化測試失敗可以重現？
向函式注入亂數產生器，或在每次測試前固定種子；失敗時記錄種子、輸入與 k。同一輸入使用多組固定種子執行，並始終與排序 oracle 對照。這既能重現特定樞紐路徑，也能確認錯誤是否跨路徑存在。