2019-03-15

在一个时间复杂度O(N2)的算法下面可以加几个时间复杂度是O(N)的算法，这样实际上时间复杂度变化不大的。
https://leetcode.com/problems/k-closest-points-to-origin/solution/

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        int N = points.length;
        int[] dists = new int[N];
        for (int i = 0; i < N; ++i)
            dists[i] = dist(points[i]);
        Arrays.sort(dists);
        int distK = dists[K-1];
        int[][] ans = new int[K][2];
        int t = 0;
        for (int i = 0; i < N; ++i)
            if (dist(points[i]) <= distK)
                ans[t++] = points[i];
        return ans;
    }
    public int dist(int[] point) {
        return point[0] * point[0] + point[1] * point[1];
    }
}

这个算法有一个问题， 就是如果选择K个的时候，如果边界的最小值有多个相等值，那么输出值就有可能多输出好几个，导致数组越界， 比如：

points = (1,3) (-1,3) (1,-3)(-1,-3);
K=1;

解决这个问题，有两个办法，
1.列出Kdist的数组并且在points里面循环遍历，一次找出来一个。但是这样时间时间复杂度就从O(Nlog(N)) 变成了O(N2)。
2.用快排（或者任意一种算法去做），做的时候用一个数组index[],来标记原先point的位置，就相当于手动实现了一个key-value的映射。。。。这样理论上时间复杂度还是快排的时间负责度。空间复杂度增加了O(N)。