Задача: 658. Find K Closest Elements
Сложность: easy

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

Целое число a ближе к x, чем целое число b, если:

|a - x| < |b - x|, или
|a - x| == |b - x| и a < b.

Пример:

Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]

👨‍💻 Алгоритм:

1⃣Бинарный поиск:
Найдите положение числа x или ближайшего к нему числа в массиве arr с помощью бинарного поиска.

2⃣Два указателя:
Используйте два указателя, чтобы расширять окно, которое содержит k ближайших к x элементов. Начните с ближайших элементов и расширяйте окно, сравнивая элементы слева и справа от текущего окна.

3⃣Сортировка:
Отсортируйте итоговый список, если это необходимо (в данном случае это не нужно, так как массив уже отсортирован).

😎 Решение:

import bisect

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        pos = bisect.bisect_left(arr, x)
        left, right = pos - 1, pos
        
        while right - left - 1 < k:
            if left == -1:
                right += 1
            elif right == len(arr) or (x - arr[left] <= arr[right] - x):
                left -= 1
            else:
                right += 1
        
        return arr[left + 1:right]

Ставь 👍 и забирай 📚 Базу знаний