題目描述:給定一個二維平面上的點陣列 points 以及整數 k,回傳距離原點 (0, 0) 最近的 k 個點。距離以歐幾里得距離計算,但可以直接比較距離的平方以避免浮點運算(x² + y²)。回傳答案的順序不限。
解題思路:問題本質是「從 n 個元素中找出最小的 k 個」,有三種主要思路:
方法一(本解):大小為 k 的最大堆 維護一個大小最多為 k 的最大堆,堆中儲存距離平方最小的 k 個點。對每個新點:
這樣堆中始終保留目前見過的最近 k 個點,最終直接輸出堆中所有元素即可。
為什麼用最大堆? 因為我們要「淘汰距離最遠的」,堆頂是距離最大值,方便比較與淘汰。堆的大小控制在 k,每次操作為 O(log k),對 n 個點總計 O(n log k),當 k 遠小於 n 時效率優異。
時間複雜度:O(n log k) — 對每個點執行一次堆的插入或刪除操作,堆的大小維持在 k,每次操作為 O(log k),共 n 個點,總計 O(n log k)。當 k << n 時顯著優於排序的 O(n log n)。
空間複雜度:O(k) — 最大堆最多儲存 k+1 個元素(每次超過 k 後立即彈出),輸出陣列另需 O(k) 空間。
1. Initialize an empty max-heap (ordered by squared distance). 2. For each point p in points: a. Compute dist_sq = p[0]^2 + p[1]^2. b. Push (dist_sq, index) onto the max-heap. c. If heap size exceeds k, pop the top (farthest point). 3. Collect all remaining points in the heap into the result array. 4. Return result.
完整排序 O(n log n):對所有點按距離平方排序,取前 k 個。實作最簡單,C++ 一行 sort 即可,但時間複雜度為 O(n log n),當 k 遠小於 n 時效率不如最大堆。
快速選擇 Quickselect O(n) 平均:類似快速排序的分治策略,每次以距離為鍵做 partition,只遞迴包含第 k 小元素的那半邊。平均時間 O(n),最壞 O(n²),但不需額外空間(in-place)。C++ STL 的 nth_element 正是此演算法的實作,使用後取前 k 個元素即可。最壞情況可用隨機化 pivot 避免。