Leetcode日记–973. K Closest Points to Origin

发布于 2020-11-09  110 次阅读


碎碎念:想买域名->不知道买啥名字->那还是不买了->立省100%。

题目如下:

We have a list of points on the plane.  Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

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]]
(The answer [[-2,4],[3,3]] would also be accepted.)
 

Note:

1 <= K <= points.length <= 10000
-10000 < points[i][0] < 10000
-10000 < points[i][1] < 10000

思路:

方法一:

暴力破解(我想到的方法),就是直接按照数组距离大小升序排序,然后选取前K个即可。

代码如下:

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        Arrays.sort(points,new Comparator<int[]>(){
            public int compare(int[] data1,int[] data2){
                return (int)(Math.pow(data1[0],2)+Math.pow(data1[1],2))-(int)(Math.pow(data2[0],2)+Math.pow(data2[1],2));
            }
        });
        return Arrays.copyOfRange(points, 0, K);
    }
}

方法二:

使用优先队列实现,其实和上面的思路差不多,只不过复杂度由O(nlogn)变成了O(klogk)。

代码如下:

class Solution {
    public int[][] kClosest(int[][] points, int K) {
//因为Java的库实现是使用小根堆实现的,因此为了使用大根堆每次移除K个Close里面的最大点,我们需要反过来,即compare函数中变成array2-array1
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] array1, int[] array2) {
                return array2[0] - array1[0];
            }
        });
        for (int i = 0; i < K; ++i) {
            pq.offer(new int[]{points[i][0] * points[i][0] + points[i][1] * points[i][1], i});
        }
        int n = points.length;
        for (int i = K; i < n; ++i) {
            int dist = points[i][0] * points[i][0] + points[i][1] * points[i][1];
            if (dist < pq.peek()[0]) {
                pq.poll();
                pq.offer(new int[]{dist, i});
            }
        }
        int[][] ans = new int[K][2];
        for (int i = 0; i < K; ++i) {
            ans[i] = points[pq.poll()[1]];
        }
        return ans;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/k-closest-points-to-origin/solution/zui-jie-jin-yuan-dian-de-k-ge-dian-by-leetcode-sol/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

方法三:(使用快排思想)

类似于快排,我们设立一个pivot值,并对每个点的欧几里得距离进行排序,每层递归函数结束时,pivot左边的应该是距离小于分界值的点,右边的应该是大于分界值的点。

我们定义函数 quickSortSelect(left, right, K) 表示划分数组points 的 [left,right] 区间,并且需要找到其中第 K个距离最小的点。

我们设pivot的数组下标为i:

①若K=i-left+1,则说明当前的pivot就是第K个距离最小的值(也就是距离最小的值中最大的一个)

②若K>i-left+1,则说明pivot左边的点不够K个,那么我们递归地对pivot右边的区间继续调用quickSortSelect(i+1,right,K-(i-left+1))。

③K<i-left+1,则说明第K个最小距离点在pivot的左边,则调用function(left,i-1,K)

最终无论如何pivot都会在K个最小的距离中最大的那个的位置上。

这个方法的期望复杂度是O(n)(但是我没搞懂是为啥),最坏空间复杂度是O(n^2).

代码如下:

class Solution {
    Random rand = new Random();

    public int[][] kClosest(int[][] points, int K) {
        int n = points.length;
        random_select(points, 0, n - 1, K);
        return Arrays.copyOfRange(points, 0, K);
    }

    public void random_select(int[][] points, int left, int right, int K) {
        int pivotId = left + rand.nextInt(right - left + 1);
        int pivot = points[pivotId][0] * points[pivotId][0] + points[pivotId][1] * points[pivotId][1];
        swap(points, right, pivotId);
        int i = left - 1;
        for (int j = left; j < right; ++j) {
            int dist = points[j][0] * points[j][0] + points[j][1] * points[j][1];
            if (dist <= pivot) {
                ++i;
                swap(points, i, j);
            }
        }
        ++i;
        swap(points, i, right);
        // [left, i-1] 都小于等于 pivot, [i+1, right] 都大于 pivot
        if (K < i - left + 1) {
            random_select(points, left, i - 1, K);
        } else if (K > i - left + 1) {
            random_select(points, i + 1, right, K - (i - left + 1));
        }
    }

    public void swap(int[][] points, int index1, int index2) {
        int[] temp = points[index1];
        points[index1] = points[index2];
        points[index2] = temp;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/k-closest-points-to-origin/solution/zui-jie-jin-yuan-dian-de-k-ge-dian-by-leetcode-sol/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

你好哇!欢迎来到雷公马碎碎念的地方:)