Для каждого числа из wishes нужно найти в catalog такое значение x, чтобы модуль
|wish − x| был минимальным, и сложить эти минимумы по всем заявкам. Это задача «ближайшая точка на числовой прямой»:
после сортировки каталога каждый запрос можно обработать бинарным поиском или перебором соседей.
Шаг 1. Пустые входы
Если каталог пуст или список пожеланий пуст, суммировать нечего - возвращайте 0.
Шаг 2. Наивное решение O(n·m)
Для каждого wish переберите все x из catalog и поддерживайте минимум Math.abs(wish − x). Простой старт для интервью, затем можно ускорить.
Шаг 3. Сортировка + бинарный поиск O((n+m) log n)
Скопируйте catalog в новый массив и отсортируйте. Для фиксированного wish ответ - на границах диапазона или между двумя соседями вокруг позиции вставки wish.
Найдите первый индекс left, где sorted[left] ≥ wish (lower_bound). Сосед слева - left − 1. Сравните два расстояния и возьмите минимум.
Шаг 4. Точное совпадение
Если при бинпоиске встретили элемент равный wish, вклад в сумму равен 0.
Типичные ошибки
- Сортировать исходный
catalogна месте - входные данные меняются и может сломаться другой код. - Забыть ветки «меньше минимума» и «больше максимума» в отсортированном массиве.
- Неверное имя функции - проверка ищет
calculateNearestRateTotal.
Готовый код
Эталон с копированием каталога перед сортировкой. Кнопка «Помощник» наберёт этот код в редакторе: в комментариях к строкам кратко сказано, что делает функция, цикл и переменные.
/**
* Считает сумму отклонений: для каждой желаемой ставки - расстояние до ближайшей в каталоге.
* @param {number[]} catalog - ставки из каталога (исходный массив не сортируем).
* @param {number[]} wishes - желаемые ставки пользователя.
* @return {number} - сумма минимальных |wish − ближайший catalog|.
*/
var calculateNearestRateTotal = function (catalog, wishes) {
// Нет данных - по смыслу задачи возвращаем 0
if (!catalog.length || !wishes.length) return 0;
// Копия каталога + сортировка: так безопасно для бинарного поиска «соседей»
const sorted = [...catalog].sort((a, b) => a - b);
const n = sorted.length; // длина отсортированного ряда
// Локальная функция: для одной желаемой ставки - минимальное расстояние до sorted
const closestGap = (wish) => {
// wish левее всего каталога - ближайший только минимальный элемент
if (wish <= sorted[0]) return sorted[0] - wish;
// wish правее всего - ближайший только максимальный элемент
if (wish >= sorted[n - 1]) return wish - sorted[n - 1];
let left = 0; // левая граница окна бинпоиска
let right = n - 1; // правая граница
// Ищем два соседних элемента sorted, между которыми лежит wish
while (left <= right) {
const mid = (left + right) >> 1; // индекс середины (целочисленное деление на 2)
if (sorted[mid] === wish) return 0; // точное попадание - отклонение 0
if (sorted[mid] < wish) left = mid + 1; // искомый интервал правее mid
else right = mid - 1; // интервал левее mid
}
// wish между sorted[right] и sorted[left]: два кандидата на ближайшего соседа
const distLeft = wish - sorted[right]; // расстояние до левого соседа
const distRight = sorted[left] - wish; // расстояние до правого соседа
return Math.min(distLeft, distRight); // берём меньшее
};
let total = 0; // накопитель итоговой суммы
for (const wish of wishes) total += closestGap(wish); // цикл по всем желаниям
return total;
};