658. Find K Closest Elements

Задача

Даны отсортированный массив arr, числа k и x. Верните k ближайших к x элементов (в порядке возрастания).

Решение

Решение

/**
 * Сложность по времени (Time Complexity): O(N - K) -> O(N)
 *   В худшем случае нам нужно уменьшить окно с размера N до размера K.
 *   Каждая итерация цикла while уменьшает размер окна на 1 (сдвигает left++ или right--).
 *   Количество итераций равно (N - K).
 *
 * Сложность по памяти (Space Complexity): O(1)
 *   Мы используем только два указателя (left, right) и несколько переменных для вычислений.
 *   Возвращаемый подмассив (arr.slice) не считается дополнительной памятью в контексте 
 *   алгоритмической сложности (или O(K) если считать выходные данные).
 */
var findClosestElements = function(arr, k, x) {
    let left = 0;
    let right = arr.length - 1;
 
    // Сужаем окно с двух сторон, пока не останется k элементов
    while (right - left + 1 > k) {
        // Смотрим, какой крайний элемент "хуже" (дальше от x)
        const distLeft = Math.abs(x - arr[left]);
        const distRight = Math.abs(x - arr[right]);
 
        // Если дистанция слева больше (или равна), удаляем левый? Нет.
        // По условию: при равенстве a < b (левый) лучше.
        // Значит, удаляем правый, ТОЛЬКО если правый строго дальше или равен?
        // Логика:
        // Если distLeft > distRight -> левый хуже -> left++
        // Если distLeft <= distRight -> правый хуже (или равен, но левый предпочтительнее) -> right--
 
        if (distLeft > distRight) {
            left++;
        } else {
            right--;
        }
    }
 
    return arr.slice(left, right + 1);
};

Решение 1

/**
 * Сложность по времени: O(log(N - K))
 * Мы используем бинарный поиск не по всему массиву, а по возможным позициям 
 * начала окна (от 0 до arr.length - k). Это очень быстро.
 *
 * Сложность по памяти: O(1)
 * Мы не создаем дополнительных структур данных, кроме возвращаемого подмассива.
 */
var findClosestElements = function(arr, k, x) {
    let left = 0;
    // Правая граница поиска — это последний возможный индекс начала окна
    let right = arr.length - k;
 
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
 
        // Магия сравнения:
        // Мы сравниваем элемент на начале окна (arr[mid]) 
        // и элемент СРАЗУ ПОСЛЕ конца окна (arr[mid + k]).
        //
        // Если x - arr[mid] > arr[mid + k] - x, это значит, что x находится 
        // "далеко" от начала окна и "ближе" к элементу за его пределами.
        // Значит, нам нужно сдвигать окно вправо.
        if (x - arr[mid] > arr[mid + k] - x) {
            left = mid + 1;
        } else {
            // Иначе (x ближе к началу или расстояния равны), 
            // мы сдвигаем/сужаем поиск влево.
            // При равенстве расстояний мы выбираем левую часть (по условию задачи).
            right = mid;
        }
    }
 
    // left укажет на начало лучшего окна
    return arr.slice(left, left + k);
};