973. K Closest Points to Origin

source: https://leetcode.com/problems/k-closest-points-to-origin/

Question

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

思路

这题的主要思路还是去微调排序算法，在排到K的时候，就返回。

堆排序

先从无子节点遍历，自底向上创建Max Heap。

然后一个个把根节点，which is the maximum, 置换下去，同时缩小heapify的范围。

/**
 * @param {number[][]} points
 * @param {number} k
 * @return {number[][]}
 */
var kClosest = function(points, k) {
    const indexes = points.map((_, i) => i);
    const cache = {};
    const getLength = (i) => {
        const [x, y] = points[indexes[i]];
        if (cache[indexes[i]] === undefined) cache[indexes[i]] = x ** 2 + y ** 2;
        return cache[indexes[i]];
    }
    const swap = (i1, i2) => {
        const v = indexes[i1];
        indexes[i1] = indexes[i2];
        indexes[i2] = v;
    };
    const heapify = (n, i) => {
        const l = i * 2 + 1;
        const r = l + 1;
        let smallest = i;
        if (l < n && getLength(l) < getLength(smallest)) smallest = l;
        if (r < n && getLength(r) < getLength(smallest)) smallest = r;
        if (smallest !== i) {
            swap(i, smallest);
            heapify(n, smallest);
        }
    };

    for (let i = Math.floor(points.length / 2) - 1; i >= 0; i--) heapify(points.length, i);

    for (let i = points.length - 1; i >= points.length - k; i--) {
        swap(0, i);
        heapify(i, 0);
    }

    return indexes.slice(points.length - k, points.length).map(i => points[i]);
};

End

其实这题就是考排序算法，就是换了一种方式。