題幹與適用場景
給定未排序整數陣列 nums 與 1 ≤ k ≤ nums.length，回傳按非遞增排序後的第 k 個元素。重複值按多個位置計數，例如 [5, 5, 4] 的第 2 大是 5，不是第 2 大的不同值。目標是平均 O(n) 時間、原地 O(1) 額外空間；面試中先說明是否可修改陣列。
面試官考察點
強回答會先將「第 k 大」轉成升序索引 target = n-k，再解釋 partition 只需保證樞紐左側不大於它、右側不小於它，未命中的一側無需繼續排序。也要說清重複值、k=1、k=n、已排序輸入，以及隨機樞紐對最壞情況的影響。
回答前需要釐清的問題
- 是否允許修改輸入？允許時可原地 partition；不允許時需複製陣列，空間變為
O(n)。 - 要第 k 大還是第 k 個不同值？前者按位置計數；後者必須跳過重複值，題意不同。
- 是否有持續流入的資料？單次陣列適合 Quickselect；串流通常用大小為
k的最小堆，複雜度O(n log k)。 - 是否必須有確定的最壞線性界？普通隨機 Quickselect 只有平均
O(n)；嚴格保證需 median-of-medians 或函式庫實作的保證。
推薦解法與推導
使用三路 partition：把區間分成「小於 pivot」「等於 pivot」「大於 pivot」。對轉換後的升序索引 target，若目標位置在 lt 左側只處理左區間；若在 gt 右側只處理右區間；落在 [lt, gt] 就回傳樞紐值。三路分區讓全是相同值的輸入一次結束，不會因重複值退化成單邊遞迴。
import random
def kth_largest(nums: list[int], k: int) -> int:
if not 1 <= k <= len(nums):
raise ValueError("k out of range")
target = len(nums) - k
left, right = 0, len(nums) - 1
while left <= right:
pivot = nums[random.randint(left, right)]
lt, i, gt = left, left, 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")每輪掃描目前區間一次。若樞紐按期望比例縮小區間，遞迴為 T(n)=T(cn)+O(n)，平均 O(n)；隨機樞紐仍可能連續選到極值，最壞 O(n²)。迴圈寫法避免遞迴堆疊，額外空間 O(1)。
替代方案與取捨
完整排序最容易驗證，時間 O(n log n)，陣列很小或後續仍要完整順序時較合適。大小為 k 的最小堆不修改陣列，單次掃描 O(n log k)、空間 O(k)，適合串流或 k 遠小於 n。C++ 的 std::nth_element 表達相同語義並只保證平均線性複雜度；可呼叫它，但要說明前後兩段不保證有序。
失敗場景、邊界與反例
- 把
target寫成k-1會求第 k 小，方向完全相反。 - 用二路分區處理
[7,7,7,...]，若每次只排除一個元素會達到O(n²)；三路分區一次吞掉等值段。 - 固定取
right為樞紐，在已排序或反向排序輸入上可能穩定退化；隨機化降低機率，但沒有確定性最壞界。 - 回傳「第 k 大不同值」不能沿用停止條件，必須在等值段計數或先去重。
- 空陣列、
k=0、k>n應在入口拒絕，不能讓索引錯誤掩蓋題意。
測試與驗證清單
用隨機陣列與 sorted(nums)[-k] 比對；再測全相同、負數與重複值、k=1、k=n、已排序及反向排序陣列。允許修改時檢查回傳值而非陣列順序。固定隨機種子重現測試，觀察比較次數隨 n 增長，不能把一次幸運執行當成複雜度證明。
追問與延伸
如何保證最壞情況仍為線性？
使用 median-of-medians 選樞紐，使每輪刪除固定比例，得到 O(n) 最壞時間；代價是常數較大，工程程式通常選隨機化或標準函式庫。
如何改成第 k 小？
將目標索引改成 k-1，比較方向維持升序 partition；也可保留第 k 大的 target=n-k 寫法，避免反轉陣列。
如何支援動態插入和多次查詢？
單次 Quickselect 會重複掃描。若只維護固定 k，可保留大小為 k 的最小堆；若需要任意秩查詢，考慮帶子樹大小的平衡樹，並依更新與查詢比例評估成本。