Наиболее эффективное решение использует формулу арифметической суммы для поиска пропущенного числа за O(n) времени с O(1) памяти.
Ключевая идея заключается в том, что сумму всех целых чисел от 1 до n можно вычислить мгновенно, используя формулу:
expected_sum = n * (n + 1) / 2
Вычтя реальную сумму массива из ожидаемой суммы, разница покажет пропущенное число.
def find_missing(lst):
n = len(lst) + 1 # n это полное количество, включая пропущенный элемент
expected_sum = n * (n + 1) // 2 # сумма полной последовательности 1..n
return expected_sum - sum(lst) # пропущенное число это разница
n чисел, но одного не хватает, поэтому len(lst) + 1 даёт нам истинное значение nexpected_sum — это то, какой должна быть сумма, если бы ни одно число не было пропущеноsum(lst) — это то, что мы на самом деле имеем[1, 2, 4, 5]n = 5, ожидаемая сумма = 151215 - 12 = 3 ✓setФормула арифметической суммы n * (n + 1) / 2 вычисляет ожидаемую сумму всех целых чисел от 1 до n за константное время, поэтому общая сложность алгоритма составляет O(n) из-за шага суммирования массива.
Новый — ещё не проверен сообществом
Вы