題目描述:給定一個未排序的整數陣列 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 大。
遍歷陣列,對每個元素:
遍歷完成後,堆中恰好保留最大的 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 個元素。
1. Initialize an empty min-heap. 2. For each number num in nums: a. Push num onto the min-heap. b. If heap size exceeds k, pop the minimum (heap top). 3. After processing all numbers, the heap contains the k largest elements. 4. Return heap.top() — the smallest among the k largest, i.e., the kth largest overall.
完整排序 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)。