215. Kth Largest Element in an Array

Kth Largest Element in an Array

題目描述：給定一個未排序的整數陣列 nums 和整數 k，回傳陣列中第 k 大的元素。注意是排序後的第 k 大（例如陣列 [3,2,1,5,6,4]，k=2 的答案是 5），允許有重複元素。

解題思路：「第 k 大」等同於「將陣列由大到小排序後的第 k 個元素」，也等同於「由小到大排序後的第 n-k+1 個元素」。

方法一（本解）：大小為 k 的最小堆 維護一個大小恰好為 k 的最小堆（min-heap）。堆中存放的是目前見過的最大 k 個元素，而堆頂就是這 k 個中最小的，亦即第 k 大。

遍歷陣列，對每個元素：

1. 推入堆中。
2. 若堆的大小超過 k，彈出堆頂（目前最小值，不可能是答案）。

遍歷完成後，堆中恰好保留最大的 k 個元素，堆頂即為第 k 大的元素。

為什麼用最小堆？ 我們要保留「最大的 k 個」，需要淘汰「不夠大的元素」。堆頂是目前 k 個中最小的，若新元素更大才有資格進入，堆頂被淘汰。C++ priority_queue 預設最大堆，使用 greater<int> 改為最小堆。

時間複雜度：O(n log k) — 遍歷 n 個元素，每次堆操作為 O(log k)（堆大小維持在 k），總計 O(n log k)。當 k 很小時（例如求最大值 k=1）效率極高，接近 O(n)。

空間複雜度：O(k) — 最小堆最多儲存 k 個元素。

完整排序 O(n log n)：對陣列排序後直接取 nums[n-k]（由小到大排序）。實作最直覺，但時間複雜度較高，且會修改原始陣列（或需額外空間複製）。

快速選擇 Quickselect O(n) 平均：以快速排序的 partition 思路，每次將 pivot 放到正確位置，判斷第 k 大在左半還是右半，只遞迴一邊。平均時間 O(n)，最壞 O(n²)，空間 O(1)（in-place）。C++ 中可用 nth_element(nums.begin(), nums.begin()+n-k, nums.end()) 直接完成，實際上是 Introselect（結合 Quickselect 與 Median-of-medians），保證最壞 O(n)。

計數排序（值域有限時）O(n + range)：若元素值域已知且範圍不大（例如 1 到 10000），可用計數陣列統計頻率，從大到小累加計數直到達到 k，即可得到答案，時間 O(n + range)。

1. 若資料以串流方式輸入，如何在每次新增元素後動態回答「目前第 k 大的元素是什麼」？
2. 若需要同時查詢多個不同的 k 值（例如第 2 大、第 5 大、第 10 大），如何設計更高效的資料結構？
3. 快速選擇演算法在最壞情況下會退化為 O(n²)，實際面試中如何向面試官解釋並提出改進方案（例如隨機化 pivot 或 Median-of-medians）？