973. K Closest Points to Origin

二刷 06/2022

Version #2 Quick Select version 1

这里是把 pivot number swap到了correct index

但是似乎没有必要，因为只要求前k个而不是求第k个

好像while(true)可以写成while(start<=end)

Time O(N)

Space O(1)

Runtime: 17 ms, faster than 91.57% of Java online submissions for K Closest Points to Origin.

Memory Usage: 118.8 MB, less than 15.14% of Java online submissions for K Closest Points to Origin.

class Solution {

    public int[][] kClosest(int[][] points, int k) {

        // Quick select

        int[][] distances = new int[points.length][2];

        for (int i = 0; i < distances.length; i++) {

            distances[i] = new int[]{(int)Math.pow(points[i][0], 2) + (int)Math.pow(points[i][1], 2), i};

        }

        int start = 0, end = distances.length - 1;

        while (true) {

            // System.out.printf("start=%d,end=%d\n", start, end);

            int mid = start + (end - start) / 2;

            swap(distances, mid, start);

            int[] pivot = distances[start];

            int left = start + 1, right = end;

            while (left <= right) {

                while (left <= right && distances[left][0] < pivot[0]) {

                    left++;

                }

                while (left <= right && distances[right][0] > pivot[0]) {

                    right--;

                }

                if (left <= right) {

                    swap(distances, left, right);

                    left++;

                    right--;

                }

            }

            // System.out.printf("left=%d,right=%d\n", left, right);

            swap(distances, start, right);

            if (right == k - 1) {

                break;

            } else if (right < k - 1) {

                start = right + 1;

            } else {

                end = right - 1;

            }

        }

        int[][] result = new int[k][2];

        for (int i = 0; i < k; i++) {

            result[i] = points[distances[i][1]];

        }

        return result;

    }

    

    private void swap(int[][] array, int a, int b) {

        int[] temp = array[a];

        array[a] = array[b];

        array[b] = temp;

    }

}

Version #1 Max Heap

写了一个很搞笑的bug就是x^2並不是x的平方，要写成x * x或者Math.pow(x, 2)

LeetCode答案有一个可以优化的地方，就是instead of pushing the x,y positions into the max heap, we can push the {distance, index} into the headp 这样每次sift up和sift down的时候不需要重新计算distance了，速度会加快

Time O(NlogK)

Space O(K)

Runtime: 73 ms, faster than 22.84% of Java online submissions for K Closest Points to Origin.

Memory Usage: 118.6 MB, less than 20.04% of Java online submissions for K Closest Points to Origin.

class Solution {

    public int[][] kClosest(int[][] points, int k) {

        if (points == null || points.length == 0 || points[0] == null || points[0].length == 0) {

            return new int[0][0];

        }

        Queue<int[]> maxHeap = new PriorityQueue<>((a, b) -> {

            long distA = a[0] * a[0] + a[1] * a[1];

            long distB = b[0] * b[0] + b[1] * b[1];

            if (distA == distB) {

                return a[0] < b[0] ? 1 : -1;

            }

            return distA < distB ? 1 : -1;

        });

        for (int[] point : points) {

            maxHeap.offer(point);

            if (maxHeap.size() > k) {

                maxHeap.poll();

            }

        }

        int[][] result = new int[k][2];

        for (int i = 0; i < k && !maxHeap.isEmpty(); i++) {

            result[i] = maxHeap.poll();

        }

        return result;

    }

}

Version #2 Quick Select

群里总监讲的，惊为天人
quick select 第k个
然后k以前的都是sort好的了

quick select还是非常难写的
有一个bug现在都还没有想明白，就是如果写成start = index + 1结果就是错的
[[68,97],[34,-84],[60,100],[2,31],[-27,-38],[-73,-74],[-55,-39],[62,91],[62,92],[-57,-67]] 5
这个case会返回4或6个答案
懂了！
是这样的，因为 一开始写的是start < end, 所以如果最后 start == end==k的时候，就不再进入循环了，就没有机会给index赋值，造成index是上一个[start, end]之间随机的数
如果改成start <= end
start = index + 1就是正确的
见下解
100.00 %
class Solution {
    private Random random = new Random();
    public int[][] kClosest(int[][] points, int K) {
        //       <=rd   >rd
        //  array[...rd...]
        int start = 0, end = points.length - 1;
        int index = 0;
        while (start <= end) {
            index = partition(points, start, end);
            //   0      K
            // start  index  end
            if (index == K) {
                break;
            }
            if (index > K) {
                end = index - 1;
            } else {
                start = index + 1;
            }
        }
        int[][] result = new int[index][2];
        for (int i = 0; i < index; i++) {
            result[i] = points[i];
        }
        return result;
    }
   
    private int partition(int[][] points, int start, int end) {
        // [start, end]
        // [0, end - start]
        int rd = start + random.nextInt(end - start + 1);
        // int rd = end;
        int[] target = points[rd];
        swap(points, rd, end);
        int left = start, right = end - 1;
        while (left <= right) {
            while (left <= right && !isLarger(points[left], target)) left++;
            while (left <= right && isLarger(points[right], target)) right--;
            if (left <= right) {
                swap(points, left, right);
                left++;
                right--;
            }
        }
        swap(points, left, end);
        return left;
    }
   
    private void swap(int[][] points, int i1, int i2) {
        int[] temp = points[i1];
        points[i1] = points[i2];
        points[i2] = temp;
    }
   
    // return true if p1 dist is larger than p2
    private boolean isLarger(int[] p1, int[] p2) {
        return p1[0] * p1[0] + p1[1] * p1[1] > p2[0] * p2[0] + p2[1] * p2[1];
    }
}


Time O(n)

100.00 %
class Solution {
    private Random random = new Random();
    public int[][] kClosest(int[][] points, int K) {
        //       <=rd   >rd
        //  array[...rd...]
        int start = 0, end = points.length - 1;
        int index = 0;
        while (start < end) {
            index = partition(points, start, end);
            //   0      K
            // start  index  end
            if (index == K) {
                break;
            }
            if (index > K) {
                end = index - 1;
            } else {
                start = index;
            }
        }
        int[][] result = new int[index][2];
        for (int i = 0; i < index; i++) {
            result[i] = points[i];
        }
        return result;
    }
   
    private int partition(int[][] points, int start, int end) {
        // [start, end]
        // [0, end - start]
        int rd = start + random.nextInt(end - start + 1);
        // System.out.println(start + " " + end + " " + rd);
        // int rd = end;
        int[] target = points[rd];
        swap(points, rd, end);
        int left = start, right = end - 1;
        while (left <= right) {
            while (left <= right && !isLarger(points[left], target)) left++;
            while (left <= right && isLarger(points[right], target)) right--;
            if (left <= right) {
                swap(points, left, right);
                left++;
                right--;
            }
        }
        swap(points, left, end);
        return left;
    }
   
    private void swap(int[][] points, int i1, int i2) {
        int[] temp = points[i1];
        points[i1] = points[i2];
        points[i2] = temp;
    }
   
    // return true if p1 dist is larger than p2
    private boolean isLarger(int[] p1, int[] p2) {
        return p1[0] * p1[0] + p1[1] * p1[1] > p2[0] * p2[0] + p2[1] * p2[1];
    }
}



Version #1 maxHeap
Time O(nlogk)
Space O(k)

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
            (a, b) -> b[0] * b[0] + b[1] * b[1] - (a[0] * a[0] + a[1] * a[1]));
        for (int[] point : points) {
            maxHeap.offer(point);
            if (maxHeap.size() > K) {
                maxHeap.poll();
            }
        }
        int[][] result = new int[maxHeap.size()][2];
        for (int i = 0; i < result.length; i++) {
            result[i] = maxHeap.poll();
        }
        return result;
    }
}