The devil is in the details. A small detail can make a big difference in code performance.

Recently with friends to study the divide-and-conquer algorithm, read “Introduction to the algorithm” feel, paper come zhongjue shallow, must know this to practice ah! Closest Points to Origin

In this article, I would like to share some of the excellent code details that THE author found while doing the problem. I hope we can learn some nutrition and enjoy it together.

Before reading, I suggest that you do the problem yourself, at least think about it, and then read on, so that it is easier to appreciate the elegance of this detail.

A, the title

973. K Closest Points to Origin

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 forExample 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]] order to also be accepted.) Note: 1 <= K <= points.length <= 10000 -10000 < points[i][0] < 10000 -10000 < points[i][1] < 10000Copy the code

They want to find the first K points closest to the origin. And you don’t care about the order of the results.

Second, the code

Skip the idle talk and go directly to the code before the improvement:


class Solution {
    public int[][] kClosest(int[][] points, int K) {
        quickSort(points, 0, points.length - 1);
        return Arrays.copyOfRange(points, 0, K);
    }
    
    private void quickSort(int[][] a, int low, int high) {
        if(low < high) {
            int pivot = partation(a, low, high);
            quickSort(a, low, pivot - 1);
            quickSort(a, pivot + 1, high); }}private int partation(int[][] a, int low, int high) {
        int[] pivot = a[low];
        int pivotDist = dist(pivot);
        
        while(low < high) {
            while(low < high && dist(a[high]) >= pivotDist) {
                high--;
            }
            a[low] = a[high];
            while(low < high && dist(a[low]) <= pivotDist) {
                low++;
            }
            a[high] = a[low];
        }
        a[low] = pivot;
        return low;
    }

    private int dist(int[] a) {
        return a[0] * a[0] + a[1] * a[1]; }}Copy the code

It took 16ms, and it was 10+ms after several attempts. The shortest solution recorded by LeetCode was 3ms. Submit the solution with 3ms, and now it takes 4ms.

Three, find the gap, become excellent

The difference is mainly in the quickSort method, which is similar to the following, adding some judgment, removing some unnecessary sorting, because the question says “You may return the answer in any order”, so You only need to find the first K smallest, There is no need to ensure that the first K are in descending order.


    private void quickSort(int[][] a, int low, int high, int K) {
        if(low < high) {
            int pivot = partation(a, low, high);
            if(pivot == K) return;
            if(pivot > K) {
                quickSort(a, low, pivot - 1, K);
            }else{
                quickSort(a, pivot + 1, high, K); }}}Copy the code

After this change, the time is also 4ms. My understanding of this code: after a quick row, the pivot (fulcrum) left side is less than or equal to it, right side is greater than or equal to it. (1) If the subscript of the pivot is equal to K, it means that the K points on the left of the pivot are the first K points with the smallest distance from the origin, and can be returned; (2) If the subscript of pivot is greater than K, then to satisfy (1), only low to pivot -1 is needed to continue the quick sort; (3) If the subscript of the pivot is less than K, then to satisfy (1), just continue the quicksort with pivot + 1 to high.

This shows the difference in thinking, my previous idea is to use quicksort to sort from small to large, and then take the first K, and this approach is to find the appropriate pivot, pivot left point is the point to find, save a lot of useless work, will use quicksort just right.

Four,

When solving the problem, pay attention to the conditions in the problem and skillfully use the appropriate algorithm. Find the gap between excellence and excellence.