這題其實就是讓你更為熟練 Heap 的操作方式，利用一些條件讓你變相去收集集合以後，找出比較接近某個值的集合範圍，再透過 Heap 將其範圍抓出來。
我們來看一下原題內容講些什麼？
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).
The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).
Example 1:
Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].
Example 2:
Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Explanation: The answer [[-2,4],[3,3]] would also be accepted.
Constraints:
給你 n 個點，每個點都有自己的 x, y 值，透過座標來算出原點跟該點的距離有多遠，請你找出 k 個離原點 (0,0) 最近的點。
這個題目其實有多種解法，一開始我們可以先用暴力解來解題，首先最先想到的就是先把距離算出來，可以先設計一個方法來計算距離。
fun calDistance(point:IntArray):Int{
return point[0]*point[0] + point[1]*point[1]
}
接著我們透過 Arrays.sort() 這個方法將其排序。
Arrays.sort(points, { p1, p2->
calDistance(p1) - calDistance(p2)
})
如此一來，我們只需要將其 points[0] 到 points[k] 的子陣列回傳即是答案。
return Arrays.copyOfRange(points, 0, k)
完整解法。
class Solution {
fun kClosest(points: Array<IntArray>, k: Int): Array<IntArray> {
Arrays.sort(points, { p1, p2->
calDistance(p1) - calDistance(p2)
})
return Arrays.copyOfRange(points, 0, k)
}
fun calDistance(point:IntArray):Int{
return point[0]*point[0] + point[1]*point[1]
}
}
如果你透過排序，那我們整體複雜度就會是 O(NLogN)，
但是這樣的解法並不是最佳的，因為我們還可以透過 Heap 來進行處理。
一樣一開始宣告一個 MinHeap 來幫我處理距離長短的問題，這樣 Root 就是距離原點最短的 Point，隨著每次加入元素，Heap 都會幫我們排序一次，因此，等到全部元素都塞入 Heap 內以後，取出前 K 個元素集合，就是我們的答案了。
程式碼如下。
class Solution {
fun kClosest(points: Array<IntArray>, k: Int): Array<IntArray> {
val minHeap = PriorityQueue<IntArray>(){ p1, p2->
calDistance(p1) - calDistance(p2)
}
for(i in points.indices){
minHeap.add(points[i])
}
return Array<IntArray>(k){minHeap.poll()}
}
fun calDistance(point:IntArray):Int{
return point[0]*point[0] + point[1]*point[1]
}
}
一開始我們塞進去 Heap ，每塞一個元素則會排序一次，所以複雜度為 O(NLogN)，
但是其實我們可以最佳化這樣的處理方式，透過以下方法就可以調整成更有效率的程式碼。
這次我們需要反過來操作，透過 MaxHeap 來進行操作，首先宣告 k 個大小的 MaxHeap，這代表什麼意思？意思就是我們把前 k 個裝進 Heap 內，距離最大的會被放在 root，此時，走訪剩下的 Points 陣列，只要透過 Heap.Peek() 這個方法，就可以偷看 Root 的值是否比陣列走訪的元素小，如果小就替換掉，如此一來，MaxHeap 裝的就會是此 Points 陣列最靠近原點 (0,0) 的集合了。
class Solution {
fun kClosest(points: Array<IntArray>, k: Int): Array<IntArray> {
val maxHeap = PriorityQueue<IntArray>(){ p1, p2 ->
calDistance(p2)-calDistance(p1)
}
for(i in 0..k-1){
maxHeap.add(points[i])
}
for(i in k..points.size-1){
if(calDistance(points[i]) < calDistance(maxHeap.peek())){
maxHeap.poll()
maxHeap.add(points[i])
}
}
return Array<IntArray>(k){maxHeap.poll()}
}
fun calDistance(point:IntArray):Int{
return point[0]*point[0] + point[1]*point[1]
}
}
由於我們一開始宣告了 k 大小的 Heap，因此，我們塞進去 k 個總共花費 O(KLogK)，接著我們走訪剩下的元素，就是 O(N-KLogK)，所以總共就是 O(KLogK + (N-K)LogK)，所以整體時間複雜度為 O(NLogK)。