Найти ближайший ресторан с учетом мест

Question

Напишите функцию, которая находит ближайшие рестораны и возвращает ближайшее целевое число предоставленных ресторанов.allLocations - это массив координат [x, y].Расстояние рассчитывается по sqrt (x ^ 2 + y ^ 2).Местоположение пользователя всегда начинается с [0,0]

function nearestResturants(totralRes,allLocations,toReturn)

пример ввода: ближайшие ресторанчики (4, [[1,1], [4,2], [7,8], [9,3])], 2)

Мой план состоял в том, чтобы создать массив объектов с местоположением и рассчитанным расстоянием для каждой координаты.Затем верните отсортированный массив, содержащий координаты, и верните сначала toReturn координаты.

function nearestResturants(totralRes,allLocations,toReturn) {
  const locs = allLocations.map(location => {
    return {
      loc: location,
      distance: calcDistance(location)
    }
 });
}

function calcDistance(location) {
  var dis = Math.pow(location[0],2) + Math.pow(location[1],2);
  return Math.sqrt(dis);
}

Вывод для locs также странный, поскольку он возвращает [объектный объект] 1. Есть ли более быстрый способ сделать это?Потому что это приведет как минимум к O(nlogn).2. как это сделать лучше и проще?

Answer 1

Есть 2 способа решить эту проблему:

1. отсортировать созданный вами массив и вернуть первые k элементы - O(nlogn)
2. ИспользоватьКуча для получения наименьшего элемента k - O(n + logn*k).

Рассмотрим следующий метод:

function nearestResturantsWithSort(totralRes,allLocations,toReturn) {
    const locs = allLocations.map(location => {
        return {loc: location, distance: calcDistance(location)};
    });
    locs.sort((a,b) => (a.distance > b.distance) ? 1 : ((b.distance > a.distance) ? -1 : 0));
    return locs.slice(0, toReturn);
}

var Heap = require('heap');
function nearestResturantsWithHeap(totralRes,allLocations,toReturn) {
    let locs = allLocations.map(location => {
        return {loc: location, distance: calcDistance(location)};
    });
    return Heap.nsmallest(locs, toReturn, function(a, b) { return a.distance - b.distance; });
}

function calcDistance(location) {
    return Math.sqrt(Math.pow(location[0],2) + Math.pow(location[1],2));
}

Я бы, конечно, рекомендовал второйметод (куча)