// Дан отсортированный по неубыванию массив целых чисел a, индекс элемента index и целое число k.

Условие

// Дан отсортированный по неубыванию массив целых чисел a, индекс элемента index и целое число k. // Необходимо вернуть в любом порядке k чисел из массива, которые являются ближайшими по значению к элементу a[index]. // Ограничения: // Размер массива 1 <= N <= 10^6; // Элементы массива: -10^9 <= a[i] <= 10^9; // Число 0 <= k <= N; // Индекс элемента 0 <= index < N.

// find_k_closest(a={2, 3, 5, 7, 11}, index=3, k=2) -> {5, 7}

Ответ

Включите a[index], затем расширяйтесь двумя указателями влево и вправо, выбирая ближайшее к нему значение. Для k=0 верните пустой список. Сложность — O(k).

При равном расстоянии можно выбрать левый элемент: порядок результата не задан. Дубликаты считаются отдельными элементами массива. Дополнительная память без результата — O(1).

def find_k_closest(a, index, k):
    if k == 0:
        return []
    target = a[index]
    result = [target]
    left, right = index - 1, index + 1
    while len(result) < k:
        if right == len(a) or (left >= 0 and target - a[left] <= a[right] - target):
            result.append(a[left])
            left -= 1
        else:
            result.append(a[right])
            right += 1
    return result

Код предполагает ограничения из условия. В языках с 32-битными числами разность лучше вычислять в расширенном типе.