LeetCode 973. K Closest Points to Origin

Problem

LeetCode 973. K Closest Points to Origin

1. 题目简述

给出某二维平面上的一些坐标，例如[1, 2]，找出这些坐标中距离原点最近的K个节点。例如：

Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]

Note:

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

2. 算法思路

这道题难倒是不难，思路也很明确，其实主要是考察数据结构的熟悉程度以及API的调用，否则写起来很麻烦。

暴力解法

首先我们需要记录每个节点与原点的距离，然后进行排序，找出前k个，并把这k个的对应的pair找出来。

用最笨的办法的话就是用个map记录一下distance和对应的index之间的关系，然后排序结束以后找出前k的distance，然后再从map中找出index，再进行遍历。这个方法很麻烦，而且耗时长。

使用Arrays.sort方法自定义排序

我们知道Arrays.sort函数可以默认排序数字类型，但是其更广泛的用法其实是自定义排序任意类型，这点和Collections.sort一个道理。

详情见：Java知识点记录——第一项

使用PriorityQueue自定义比较方式

同上，只不过queue也是一种List，可以用Comparator来自定义比较方式从而初始化一个小顶堆。这里有两种方式，多种写法。

分治法

找top k问题的常见套路，写一个helper函数来找一个合适的mid，其实并不需要全局有序，只要部分有序就可以了。

3. 解法

暴力解法代码

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        Map<Integer, List<Integer>> distanceMap = new HashMap();
        List<Integer> distances = new ArrayList();

        for (int i = 0; i < points.length; i++) {
            int distance = points[i][0] * points[i][0] + points[i][1] * points[i][1];
            distances.add(distance);
            if (!distanceMap.containsKey(distance)) {
                distanceMap.put(distance, new ArrayList<Integer>());
            }
            distanceMap.get(distance).add(i);
        }

        Collections.sort(distances);

        int[][] res = new int[K][2];
        int count = 0, index = 0;
        while (count < K) {
            int target = distances.get(index);
            List<Integer> targetIndexes = distanceMap.get(target);
            for (int i = 0; i < targetIndexes.size(); i++) {
                int x = targetIndexes.get(i);
                res[count][0] = points[x][0];
                res[count][1] = points[x][1];
                count++;
            }
            index++;
        }

        return res;
    }
}

使用Arrays.sort()

class Solution {
    // 解法1
    public int[][] kClosest(int[][] points, int K) {
        int[][] res = new int[K][2];
        int index = 0;

        Arrays.sort(points, (point1, point2) -> point1[0] * point1[0] + point1[1] * point1[1] - point2[0] * point2[0] - point2[1] * point2[1]);

        while (index < K) {
            res[index] = points[index];
            index++;
        }

        return res;
    }

    // 解法2
    public int[][] kClosest(int[][] points, int K) {
        Arrays.sort(points, Comparator.comparing(p -> p[0] * p[0] + p[1] * p[1]));
        return Arrays.copyOfRange(points, 0, K);
    }
}

使用PriorityQueu+Comparator

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        // 要大顶堆，所以返回p2 - p1
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>((p1, p2) -> p2[0] * p2[0] + p2[1] * p2[1] - p1[0] * p1[0] - p1[1] * p1[1]);

        for (int[] p : points) {
            queue.offer(p);
            if (queue.size() > K) {
                queue.poll();
            }
        }

        int[][] res = new int[K][2];
        while (K > 0) {
            res[--K] = queue.poll();
        }

        return res;
    }

    public int[][] kClosest(int[][] points, int K) {
        // 要大顶堆，所以返回p2 - p1
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>((p1, p2) -> p1[0] * p1[0] + p1[1] * p1[1] - p2[0] * p2[0] - p2[1] * p2[1]);

        queue.addAll(Arrays.asList(points));

        int[][] res = new int[K][2];
        while (K > 0) {
            res[--K] = queue.poll();
        }

        return res;
    }
}

使用分治法找top k

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        int l = 0, r = points.length - 1,

        while (l <= r) {
            int mid = helper(points, l, r);
            if (mid == K) {
                break;
            } else if (mid < K) {
                l = mid + 1;
            } else if (mid > K) {
                r = mid - 1;
            }
        }

        return Arrays.copyOfRange(points, 0, K);
    }

    private int helper(int[][] points, int l, int r) {
        int[] pivot = points[l];
        while (l < r) {
            while (l < r && compare(points[r], pivot)) {
                r--;
            }
            points[l] = points[r];
            while (l < r && compare(pivot, points[l])) {
                l++;
            }
            points[r] = points[l];
        }
        points[l] = pivot;
        return l;
    }

    // p1是否大于p2
    private boolean compare(int[] p1, int[] p2) {
        return (p1[0] * p1[0] + p1[1] * p1[1] - p2[0] * p2[0] - p2[1] * p2[1]) >= 0;
    }
}