Missing Number

Q: Какова временная сложность задачи «Пропущенное число»?

Решения с использованием суммы и XOR работают за время O(n) и требуют O(1) дополнительной памяти, поскольку считывают каждое значение один раз и хранят одно число. Поиск в списке для каждого кандидата занимает O(n²) . Предварительная сортировка и поиск пропуска занимают O(n log n) .

ЛегкоБитовые операции Математика и моделирование

+10

Дан список nums из n различных целых чисел, каждое из которых находится в диапазоне от 0 до n. В диапазоне от 0 до n содержится n+1 число, поэтому ровно одного из них нет в списке. Верните это отсутствующее число.

Функция

missingNumber(nums: integer-array) → integer

numsinteger-array: n различных целых чисел из диапазона от 0 до n в любом порядке
Возвращаетinteger: единственное число от 0 до n, которого нет в nums

Ограничения

n == nums.length
1 ≤ n ≤ 10⁴
0 ≤ nums[i] ≤ n
Все значения в nums различны.

Примеры

Ввод: nums = [4, 2, 0, 1]
Вывод: 3
Пояснение: В списке 4 значения, поэтому диапазон — от 0 до 4. Он содержит 0, 1, 2 и 4, а 3 — единственное число, которому нет соответствия.

+13 скрытых тестов при отправке

Дополнительный вопрос

Если бы список был отсортирован, смогли бы вы найти пропущенное число за O(log n) с помощью бинарного поиска?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Ты точно знаешь, что должен содержать список: все целые числа от 0 до n. Искать каждое из этих чисел по очереди можно, но для каждого числа придётся полностью просканировать список заново. Вместо этого сведи весь диапазон и список к одному сводному значению — сумме или результату операции XOR, — и разница между ними даст пропущенное число. Для этого потребуется один проход и никакой дополнительной памяти.

Проверьте каждый вариант

Верно, но не успевает на самых больших тестах

Идея

Ответ — одно из n+1 чисел от 0 до n. Перебирай их по порядку и для каждого просматривай список. Первое число-кандидат, которому не соответствует ни одно значение, и есть пропущенное число.

Это верно, потому что каждое число в диапазоне либо есть в списке, либо является ответом, а в списке нет дубликатов, поэтому поиск не найдёт ровно один кандидат.

Это медленно, потому что для каждого кандидата приходится просматривать до n значений. Когда пропуск находится ближе к верхней границе, приходится искать почти каждый кандидат: при n = 10^4 и пропуске ближе к концу это около 5 × 10^7 сравнений. Удвоение длины списка увеличивает объём работы в четыре раза.

Алгоритм

Перебирай candidate от 0 до n включительно.
Ищи в nums значение, равное candidate.
Если поиск его находит, переходи к следующему кандидату.
Если поиск заканчивается без совпадения, верни candidate.

def missingNumber(nums):
    n = len(nums)
    for candidate in range(n + 1):
        # "in" on a list scans it from the start: O(n) per candidate.
        if candidate not in nums:
            return candidate
    return -1

Вычтите сумму из ожидаемой суммы

Идея

Если бы ничего не пропало, список содержал бы все числа от 0 до n, а их сумма равна n(n+1)/2. Фактический список — это полный набор, из которого убрали одно число, поэтому его сумма меньше ровно на это число.

Для [4, 2, 0, 1] значение n равно 4, а сумма полного диапазона равна 4 × 5 / 2 = 10. Сумма чисел в списке равна 7, и 10 минус 7 дает 3.

За один проход можно сложить числа в списке, поэтому время выполнения составляет O(n), а хранить нужно только одну текущую сумму. Здесь полная сумма не превышает примерно 5 × 10^7, что помещается в 32-битное целое число. Для значительно больших значений n формула переполняет 32-битный тип int, поэтому в версиях на Java, C, C++, C# и Rust вычисления выполняются с 64-битными числами.

Алгоритм

Пусть n — длина nums.
Вычисли полную сумму n(n+1)/2.
Сложи все значения в nums.
Верни полную сумму минус сумму списка.

def missingNumber(nums):
    n = len(nums)
    expected = n * (n + 1) // 2
    return expected - sum(nums)

XOR-ните индексы со значениями

Идея

XOR сокращает одинаковые пары. a ^ a равно 0, a ^ 0 равно a, и порядок операций не имеет значения. Поэтому, если применить XOR к набору чисел, в котором каждое число встречается дважды, кроме одного значения, пары сократятся, и останется это значение.

Собери такой набор из условия задачи: индексы от 0 до n плюс значения в nums. Число из списка встречается один раз как индекс и один раз как значение, поэтому оно сокращается. Пропущенное число встречается только как индекс, поэтому оно остаётся. Цикл перебирает индексы от 0 до n-1, поэтому начни с результата n, чтобы учесть последний индекс.

Для [4, 2, 0, 1]: начни с 4, затем примени XOR к 0 и 4, 1 и 2, 2 и 0, 3 и 1. Все 4, 2, 1 и 0 сокращаются, и остаётся 3. Это один проход с одной накапливаемой переменной, и, в отличие от суммы, значение никогда не превышает разрядность, уже используемую n, поэтому переполнение невозможно.

Алгоритм

Установите result равным n, длине nums.
Для каждого индекса i выполните XOR для result, i и nums[i].
Верните result.

def missingNumber(nums):
    # Start with n, the one index the loop below never reaches.
    result = len(nums)
    for i, value in enumerate(nums):
        result ^= i ^ value
    return result

Ловушки и крайние случаи

Большинство неправильных ответов связано с двумя концами диапазона.

Забывают, что само n тоже может отсутствовать. В [0, 1, 2] ответ — 3, а это не индекс списка. В версии с XOR нужно начинать с n, а отсортированный проход, который ищет первое nums[i] != i, должен возвращать n, если все позиции совпадают.
Используют неправильный размер диапазона. Числа идут от 0 до n, то есть всего их n+1, поэтому полная сумма равна n(n+1)/2, а не (n-1)n/2.
Предполагают, что 0 всегда присутствует. В [1] ответ — 0, и код, который начинает поиск с 1, его пропустит.
Переполнение в версии с суммой. При 32-битной арифметике произведение n(n+1) переполняется, когда n превышает примерно 46 000, ещё до того, как деление на 2 может помочь, а само значение n(n+1)/2 перестаёт помещаться примерно при 65 000. Используйте 64-битную арифметику или XOR.

Частые вопросы4

Какова временная сложность задачи «Пропущенное число»?

Решения с использованием суммы и XOR работают за время O(n) и требуют O(1) дополнительной памяти, поскольку считывают каждое значение один раз и хранят одно число. Поиск в списке для каждого кандидата занимает O(n²). Предварительная сортировка и поиск пропуска занимают O(n log n).

Почему XOR находит пропущенное число?

Исключающее ИЛИ числа с самим собой даёт 0, исключающее ИЛИ с 0 ничего не меняет, и порядок не имеет значения. Если применить исключающее ИЛИ ко всем индексам от 0 до n вместе со всеми значениями, каждое число из списка встречается дважды и взаимно уничтожается. Пропущенное число встречается только один раз — как индекс, поэтому оно и является результатом.

Следует ли использовать формулу суммы или XOR?

Оба требуют одного прохода и постоянного объёма памяти. Сумму объяснить проще, но при 32-битной арифметике произведение n(n+1) переполняется, когда n превышает примерно 46 000, поэтому нужна 64-битная арифметика. XOR никогда не переполняется. В Python, Ruby и других языках с целыми числами неограниченной точности разница исчезает.

Можешь решить задачу «Пропущенное число» с помощью хеш-множества?

Да. Поместите все значения в множество, затем проверьте числа от 0 до n и верните первое число, которого нет в множестве. Это выполняется за время O(n), но использует дополнительную память O(n), чего позволяют избежать методы с суммой и XOR.

Python

def missingNumber(nums):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

nums = [4, 2, 0, 1]

Ожидается

Missing Number

Функция

Ограничения

Примеры

Подсказки

Решение

Проверьте каждый вариант

Вычтите сумму из ожидаемой суммы

XOR-ните индексы со значениями

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи