javascript - 找到距离原点 (0, 0) 最近的 K 个点

Question

问题是，给定一个坐标列表，确定离原点最近的 k 个坐标的数量。

我已经能够确定点和原点之间的距离，但是在过滤最近的 k 个点时，我迷路了。我决定将此逻辑放在第二个 for 循环中，将距离数组从最近到最远排序，然后推送小于 K 的值。

function kClosest(points, k) {
    let length = [];
    let arr = [];
    let result = [];
    let a = 0;
    let b = 0;

    for (let i = 0; i < points.length; i++) {
        a = points[i][0]; //x coord
        b = points[i][1]; //y coord (y will always be second number or '1')
        length.push(parseFloat(calcHypotenuse(a, b).toFixed(4)))
        arr.push([points[i], length[i]])
    }

    function calcHypotenuse(a, b) {
        return (Math.sqrt((a * a) + (b * b)));
    }

    for (let i = 0; i < k; i++) {
        arr = arr.sort();
        result.push(arr[i][0])
    }
    return result;
}



console.log(kClosest([
    [-5, 4],
    [-6, -5],
    [4, 6]
], K = 2))

预期输出:[-5, 4], [4, 6]//我有 [-5, 4], [-6, -5]

Answer 1

对整个数组进行排序是一种浪费，甚至可能是不可能的。这很浪费，因为问题没有要求所有元素的总排序，甚至没有要求 k。元素。使用基于比较的排序进行排序需要 O(n log(n))时间。更一般地说，如果输入是数字流，将它们全部存储在内存中并对其进行排序甚至可能是不可能的。

我不太了解 JavaScript，但在一般算法领域，我们可以使用以下两种方法之一更快地解决这个问题:

1. 使用 Max Priority Queue :创建一个最大 PQ，其顺序基于与原点的距离。继续插入最大 PQ 中的元素，每当大小超过 k 时, 删除顶部元素(最大值)。最后，PQ 将有 k最小的元素。空间复杂度:O(k) ，时间复杂度:O(n log(k)) k << n , 可能接近 O(n) .
2. 使用Quick-select :在输入上运行快速选择 k 次。这假设输入适合内存(空间 O(n) )，但在 O(nk) 中运行时间，对于 k << n , 可能接近 O(n) .