如何用 Quickselect 在含重複值的陣列中找第 k 大元素？

題幹與適用場景

給定未排序整數陣列 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] 就回傳樞紐值。三路分區讓全是相同值的輸入一次結束，不會因重複值退化成單邊遞迴。

python

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 的最小堆；若需要任意秩查詢，考慮帶子樹大小的平衡樹，並依更新與查詢比例評估成本。