Leetcode題解 Python & C#：五月挑戰DAY30 K Closest Points to Origin

給一串座標 Points ，回傳 K 個離(0, 0)最近的點。

要知道距離的算法，因為是找跟(0, 0)的距離，所以用 P[0]**2 + P[1]**2，就能作為比較值。(其開根號是距離)

不難，重點要放在如何排序。

使用內建的 sort() 功能就能快速排序，如同官方方法，用 sorted(points, key:lambda x: x[0]**2+x[1]**2)，能實現排序，

又不會多使用空間，是最佳解之一。

時間是 O(nlogn)，就是排序法(sort)的時間吧。

換個想法，有什麼排序法夠快，最好可以快速找到最小值？ min heap。

不然用hashtable以距離作分類，由小開始，加到K個就回傳，這也不用把整個points重新排序。

Python

class Solution:
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        import heapq
        heap = []
        for p in points:
            heapq.heappush(heap, [p[0]**2+p[1]**2, p])
        return [heapq.heappop(heap)[1] for _ in range(K)]

C#

public class Solution {
    public int[][] KClosest(int[][] points, int K) {
        var rank = new Dictionary>();
        foreach(var p in points)
        {
            int dis = p[0]*p[0] + p[1]*p[1];
            if(!(rank.ContainsKey(dis)))
                rank[dis] = new List();
            rank[dis].Add(p);
        }
        var sortedKeys = new List(rank.Keys);
        sortedKeys.Sort();
        int count = 0;
        List result = new List();
        foreach(int key in sortedKeys)
        {
            foreach(var p in rank[key])
            {
                result.Add(p);
                count += 1;
                if(count == K)
                {
                    return result.ToArray();
                }
            }
        }
        
        return result.ToArray();
    }
}