#973. K Closest Points to Origin

題目描述

給你一個points陣列，points[i] = [x₁,y₂]表示位於X-Y平面座標上的點，還有一個整數k，回傳最靠近原點[0,0]的k個點。

X-Y平面上的兩點之間的距離使用歐幾里得距離，例子：√(x¹ - x²)2 + (y¹ - y²)2。

回傳的答案可以用任何順序排序，答案是保證唯一的除了排序的順序。

限制條件

1 <= k <= points.length <= 10⁴
-10⁴ <= x_i, y_i <= 10⁴

解題思路

Calculate & Sort

用幾個分解的步驟來處理陣列。

1.計算每個點的距離，用多元組(tuple)打包距離和座標儲存進List中。 2.整理List，按照小到大排序。 3.取出K個點並回傳答案。

public class Solution { 
    public int[][] KClosest(int[][] points, int k) {
        var l = new List<(double,int[])>();
        foreach(var i in points){
            l.Add((Math.Sqrt(i[0] * i[0]+i[1] * i[1]),i));
        }
        l.Sort(CompareFirstElement);
        var ans = new List<int[]>();
        for(int i=0;i<k;i++){
            (double v,int[] p) = l[i];
            ans.Add(p);
        }
        return ans.ToArray();
    }
    public int CompareFirstElement((double v,int[] p) v1,(double v,int[] p) v2){
        if(v1.v<v2.v) return -1;
        else return 1;
    }
}

複雜度分析：

時間複雜度：計算每個距離花費N，Sort()花費n * logn，取出k個值花費k，因此時間複雜度為O(n * logn)。
空間複雜度：空間複雜度為O(n)，

Improvement

利用Comparer直接計算並且排續。

public class Solution { 
	public int[][] KClosest(int[][] points, int k) {
        DistanceCompare dc = new DistanceCompare();
        Array.Sort(points,dc);        
        return points[..k];
    }
    public class DistanceCompare : IComparer<int[]>{
        public int Compare(int[] x, int[] y){            
            int a = x[0]*x[0]+x[1]*x[1];
            int b = y[0]*y[0]+y[1]*y[1];
            return a<b?-1:1;
        }
    }    
}

複雜度分析：

時間複雜度：計Sort()花費n * logn，取出k個值花費k，因此時間複雜度為O(n * logn)。
空間複雜度：空間複雜度為O(1)。

學習重點

Sort
Compare