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

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. 使用最大优先级队列：根据与原点的距离排序创建最大 PQ。继续插入最大 PQ 中的元素，每当大小超过 时k，删除顶部元素（最大值）。最后，PQ 将具有k最小的元素。空间复杂度：O(k)，时间复杂度：O(n log(k))对于k << n，可能接近于O(n)。
2. 使用快速选择：对输入运行快速选择 k 次。这假设输入适合内存（空间O(n)），但按O(nk)时间运行，对于k << n，可能接近O(n)。

Answer 2

我建议为此使用自定义排序 - 您可以传递Array.sort()比较函数，如下所示：

function kClosest(points, k) {

    //sorts the array in place
    points.sort((point1, point2) => {
        const distanceFromOrigin1 = getDistanceFromOrigin(point1);
        const distanceFromOrigin2 = getDistanceFromOrigin(point2);

        //sort by distance from origin, lowest first
        return distanceFromOrigin1 - distanceFromOrigin2;
    });

    //returns first k elements
    return points.slice(0, k);
}

function getDistanceFromOrigin(point) {
    const [x, y] = point; //array destructuring
    return (x*x) + (y*y);
}

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

有关自定义排序的更多详细信息，请参阅https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort 。