First Missing Positive

+10

Дан неотсортированный массив целых чисел nums. Верните наименьшее положительное целое число (не меньше 1), которого нет в nums. Массив может содержать отрицательные числа, нули, повторяющиеся значения и числа, намного превышающие его длину.

Функция

firstMissingPositive(nums: integer-array) → integer

numsinteger-array: неотсортированные целые числа, которые могут повторяться и быть отрицательными, нулевыми или очень большими
Возвращаетinteger: наименьшее положительное целое число, отсутствующее в nums

Ограничения

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Значения не расположены в каком-либо определённом порядке и могут повторяться.

Примеры

Ввод: nums = [5, -2, 1, 3, 2, 9]
Вывод: 4
Пояснение: 1, 2 и 3 есть в массиве, а 4 нет, поэтому ответ — 4. 5 и 9 не имеют значения, если отсутствует меньшее значение.

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

Сможешь найти ответ за время O(n), используя только O(1) дополнительной памяти?

Подсказки

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

Открыто 0 из 3

Решение

Сортировка занимает время O(n log n), а хеш-множество — дополнительную память O(n). Существует ограничение, которое лучше обоих вариантов: n значений покрывают не более n чисел из диапазона от 1 до n+1, поэтому ответ не превышает n+1. Важны только значения от 1 до n, а в массиве есть n ячеек, чтобы их записать, поэтому дополнительная память сокращается до O(1).

Попробуйте каждого кандидата с помощью полного сканирования

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

Идея

Проверяй числа 1, 2, 3, ... по порядку. Для каждого числа просматривай весь массив и возвращай первое число, которое не будет найдено при просмотре. Согласно границе, ты никогда не проверяешь числа больше n+1.

Когда массив содержит числа от 1 до n, в среднем каждое число находится примерно на середине массива, поэтому при n = 10^4 требуется около n²/2 = 5 × 10^7 сравнений.

Алгоритм

Установи candidate равным 1.
Просматривай nums в поисках элемента, равного candidate, остановившись на первом совпадении.
Если совпадений нет, верни candidate.
Иначе прибавь 1 к candidate и просканируй снова. Ты никогда не выйдешь за пределы n+1.

def firstMissingPositive(nums):
    n = len(nums)
    # n values cannot cover all of 1..n+1, so one of these candidates is missing
    for candidate in range(1, n + 2):
        found = False
        for num in nums:
            if num == candidate:
                found = True
                break
        if not found:
            return candidate

Отметьте значения от 1 до n в массиве флагов

Идея

Поскольку ответ не превышает n+1, пропусти все значения меньше 1 или больше n. Логический массив present длины n+1 записывает остальные значения, поэтому такое значение, как 10^9, никогда не сохраняется. Верни первое v от 1 до n, у которого флаг равен false, или n+1, если установлены все флаги.

В первом примере n = 6: устанавливаются флаги для 1, 2, 3 и 5, значения -2 и 9 пропускаются, а первый неустановленный флаг — 4. Два линейных прохода занимают O(n) времени, а флаги требуют O(n) памяти.

Алгоритм

Создай present из n+1 флагов, установленных в false.
Для каждого значения v в nums, для которого выполняется 1 ≤ v ≤ n, установи present[v] в true.
Верни первое значение v от 1 до n, флаг которого равен false.
Если такого значения нет, верни n+1.

def firstMissingPositive(nums):
    n = len(nums)
    # present[v] says whether v is in nums; only 1..n can matter
    present = [False] * (n + 1)
    for num in nums:
        if 1 <= num <= n:
            present[num] = True
    for v in range(1, n + 1):
        if not present[v]:
            return v
    return n + 1

Помести каждое значение в отдельный слот

Идея

Значению v соответствует индекс v-1. Когда каждое значение от 1 до n находится на своём месте, первый индекс i, в котором находится не i+1, и даёт ответ.

На каждом индексе перемещайте значение на его место, пока оно находится в диапазоне от 1 до n и нужное место ещё не занято этим значением. Вернувшееся значение тоже может потребовать перемещения. Проверка нужного места, а не i, позволяет остановиться на дубликатах: в [1, 1] вторая 1 видит 1 по индексу 0 и остаётся на месте.

В первом примере индекс 0 отправляет 5 на своё место, а затем — вернувшуюся 2; позже 1 и 3 занимают свои места, оставляя [1, 2, 3, -2, 5, 9]: индекс 3 — первый неверный слот, поэтому ответ — 4.

Каждый обмен окончательно ставит одно значение на своё место, поэтому внутренние циклы выполняют не более n обменов суммарно: время O(n) и память O(1), кроме R, где создаётся копия изменяемого вектора.

Алгоритм

Для каждого индекса i от 0 до n-1:
Пока 1 ≤ nums[i] ≤ n и nums[nums[i]-1] ≠ nums[i], меняйте местами nums[i] и nums[nums[i]-1].
После прохода размещения найдите первый индекс i, для которого nums[i] ≠ i+1, и верните i+1.
Если каждая ячейка содержит своё значение, верните n+1.

def firstMissingPositive(nums):
    n = len(nums)
    for i in range(n):
        # Keep swapping until slot i holds a value that has no slot or is already home
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            home = nums[i] - 1
            nums[i], nums[home] = nums[home], nums[i]
    # The first slot that does not hold its own value names the answer
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

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

Останавливать перестановки, когда nums[i] == i+1, вместо того чтобы остановиться, когда в нужной позиции уже находится правильное значение. Для [1, 1] две единицы будут меняться местами бесконечно.
Использовать if вместо while для перестановки. В первом примере число 2, вернувшееся с индекса 4, так и не попадёт на индекс 1, и вы вернёте 2 вместо 4.
Сначала записывать nums[i] = nums[nums[i]-1], а затем снова индексировать по nums[i]: так будет прочитан домашний индекс после его изменения. Сначала сохраните домашний индекс.
Пропускать проверку диапазона, из-за чего 0, -2 или 10^9 указывают на индекс за пределами массива.
Возвращать n, когда все ячейки на своих местах. Для [4, 2, 1, 3] ответ — 5.

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

Какова временная сложность алгоритма First Missing Positive?

Решение с размещением работает за время O(n) и использует O(1) дополнительной памяти. Цикл while находится внутри цикла for, но каждая перестановка помещает значение на его окончательный индекс, поэтому за весь проход выполняется не более n перестановок. Вариант с массивом флагов работает за время O(n) и использует O(n) памяти, а поиск для каждого кандидата занимает O(n²).

Почему ответ никогда не бывает больше n+1?

Числа от 1 до n+1 — это n+1 различных значения, а массив длины n содержит не более n различных значений, поэтому одно из них отсутствует. Ответ равен n+1 ровно в том случае, если массив содержит все значения от 1 до n.

Изменяет ли решение на месте входной массив?

Да, он переставляет значения. Если вызывающему коду нужен исходный порядок, сначала скопируйте массив — это снова увеличит дополнительные затраты памяти до O(n). Другой метод на месте заменяет каждое значение вне диапазона от 1 до n на n+1, а затем отмечает наличие v, делая nums[v-1] отрицательным; он тоже изменяет массив.

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

Тест #1

Тест #2

Тест #3

Аргумент

nums = [5, -2, 1, 3, 2, 9]

Ожидаемый вывод

First Missing Positive

Функция

Ограничения

Примеры

Подсказки

Решение

Попробуйте каждого кандидата с помощью полного сканирования

Отметьте значения от 1 до n в массиве флагов

Помести каждое значение в отдельный слот

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

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

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