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

Условие

/ * Дан отсортированный по неубыванию список целых чисел a, индекс элемента index и целое число k. Необходимо вернуть в любом порядке k чисел из списка, которые являются ближайшими по значению к элементу a[index].

a=[2, 3, 5, 7, 11], index=3, k=2 -> [5, 7] a=[4, 12, 15, 15, 24], index=1, k=3 -> [12, 15, 15] a=[2, 3, 5, 7, 11], index=2, k=2 -> [3, 5] или [5, 7]

• /

Ответ

Начните с a[index], затем расширяйте два указателя влево и вправо, выбирая ближайшее значение. Сам исходный элемент входит в k чисел, как показывают примеры.

def closest(a, index, k):
    if not 0 <= index < len(a) or not 0 <= k <= len(a):
        raise ValueError('invalid index or k')
    if k == 0:
        return []
    left, right = index - 1, index + 1
    result = [a[index]]
    while len(result) < k:
        if right == len(a) or (left >= 0 and
                a[index] - a[left] <= a[right] - a[index]):
            result.append(a[left])
            left -= 1
        else:
            result.append(a[right])
            right += 1
    return result

Сложность O(k), память O(k) для результата. При равном расстоянии выбирается левый элемент; условие разрешает любой из равных вариантов. Python-целые не переполняются при вычитании крайних значений.