Функция, которая заполняет пропущенные числа, чтобы создать полную последовательность

Question

Я пытаюсь создать функцию, которая будет заполнять любые пропущенные числа между двумя числами в списке. Исходный список должен быть изменен и не может быть новым.

Например: [13,15,20] вернет [13,14,15,16,17,18,19,20].

Обратите внимание, что я не могу использовать функцию диапазона.

Вот мой код:

def complete(list1):
    i= 0
    if len(list1) > 1:
        for number in list1:
           if number - list1[i+1] != -1:
               number += 1
               list1.insert(i + 1, number)
           i += 1
        return list1
    else:
        return list1

Я получил ошибку "индекс списка вне диапазона".

Answer 1

Вот источник вашей ошибки:

...
for number in list1:
    if number - list1[i+1] != -1:
        ...
    i += 1

По существу, наступает момент (который является последним number в list1), когда i+1 выводит вас за пределы и Вы не делаете ничего, чтобы предотвратить это. Индексирование сложно, поэтому я хотел бы предложить подход без индексации (ну, почти). Кстати, из вашего комментария к ответу Bonfire я вижу, что задача состоит в том, чтобы изменить оригинальные списки на месте. В то время как изменение аргументов считается очень плохой практикой кодирования в наши дни, вот относительно эффективный способ сделать это:

import typing as t

def complete_sequence(partial: t.List[int]) -> t.List[int]:
    # edge case
    if len(partial) < 2:
        return partial
    # a lookup table for numbers we already have
    observed = set(partial)
    # append numbers we don't have
    start = partial[0]
    stop = partial[-1]
    num = start + 1
    while num < stop:
        if not num in observed:
            partial.append(num)
        num += 1
    # in-place sort
    partial.sort()
    return partial

Как видите, вместо вставки значений между существующими числами (оплачивая O (n) время для каждой вставки) мы можем просто добавить все (O (1) на вставку) и отсортировать. Это не только упрощает логику c (нам больше не нужно отслеживать эти надоедливые индексы), но и уменьшает сложность вычислений по времени с O (n ^ 2) до O (n * log (n)).

Answer 2

Чтобы добиться того, что вы хотите сделать, я внес некоторые изменения в логи c:

def complete(list1):
    if len(list1) < 2 : return list1

    num = list1[0]
    i = -1

    while num < list1[-1]:
        num += 1
        i += 1

        if num in list1: continue

        if i < len(list1) - 1:
            list1.insert(i + 1, num)
        else:
            list1.append(num)

    return list1

print(complete([13, 14, 20]))
#  [13, 14, 15, 16, 17, 18, 19, 20]

print(complete([13, 14, 15]))
#  [13, 14, 15]