Найти K ближайших точек к началу координат (0, 0)

Question

Проблема заключается в том, что, учитывая список координат, определите количество k координат, которые находятся ближе всего к началу координат.

Мне удалось определить расстояние между точками и началом координат, однако при фильтрации дляБлижайшие k очков, я потерялся.Я решил поместить эту логику во второй цикл for, отсортировать массив расстояний от ближайшего к дальнему и выдвинуть значения, которые меньше К.

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, но в общем алгоритмическом рассмотрении мыможно решить эту проблему быстрее, используя один из следующих 2 методов:

1. Использование Max Приоритетной очереди : Создать максимальный 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.