First Missing Positive

+10

Otrzymujesz nieposortowaną tablicę liczb całkowitych nums. Zwróć najmniejszą dodatnią liczbę całkowitą (1 lub większą), która nie występuje w nums. Tablica może zawierać liczby ujemne, zera, powtarzające się wartości oraz wartości znacznie większe od jej długości.

Funkcja

firstMissingPositive(nums: integer-array) → integer

numsinteger-array: nieposortowane liczby całkowite, które mogą się powtarzać i być ujemne, równe zero lub bardzo duże
Zwracainteger: najmniejsza dodatnia liczba całkowita, której brakuje w nums

Ograniczenia

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Wartości nie są uporządkowane w żaden szczególny sposób i mogą się powtarzać.

Przykłady

Wejście: nums = [5, -2, 1, 3, 2, 9]
Wyjście: 4
Wyjaśnienie: 1, 2 i 3 są w tablicy, a 4 nie, więc odpowiedzią jest 4. 5 i 9 nie mają znaczenia, gdy brakuje mniejszej wartości.

Pytanie dodatkowe

Czy potrafisz znaleźć odpowiedź w czasie O(n), używając tylko O(1) dodatkowej pamięci?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Sortowanie zajmuje czas O(n log n), a zbiór haszujący wymaga dodatkowej pamięci O(n). Ograniczenie przewyższa oba te rozwiązania: n wartości obejmuje najwyżej n liczb z zakresu od 1 do n+1, więc odpowiedź wynosi najwyżej n+1. Liczą się tylko wartości od 1 do n, a tablica ma n miejsc, aby je zapisać, więc dodatkowa pamięć spada do O(1).

Wypróbuj każdego kandydata, wykonując pełne skanowanie

Poprawne, ale nie kończy się na największych testach

Intuicja

Testuj kandydatów 1, 2, 3, ... po kolei. Dla każdego przeskanuj całą tablicę i zwróć pierwszego kandydata, którego skanowanie nie znajdzie. Z ograniczenia wynika, że nigdy nie testujesz wartości większej niż n+1.

Gdy tablica zawiera wartości od 1 do n, każdy kandydat jest znajdowany średnio w połowie skanowania, więc dla n = 10^4 koszt wynosi około n²/2 = 5 × 10^7 porównań.

Algorytm

Ustaw candidate na 1.
Przeszukaj nums w poszukiwaniu elementu równego candidate, zatrzymując się na pierwszym takim elemencie.
Jeśli żaden element nie pasuje, zwróć candidate.
W przeciwnym razie dodaj 1 do candidate i przeszukaj ponownie. Nigdy nie przekroczysz 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

Oznacz wartości od 1 do n w tablicy flag

Intuicja

Ponieważ odpowiedź wynosi co najwyżej n+1, pomiń każdą wartość mniejszą niż 1 lub większą niż n. Tablica wartości logicznych present o długości n+1 zapisuje pozostałe wartości, więc wartość taka jak 10^9 nigdy nie jest przechowywana. Zwróć pierwsze v od 1 do n, którego flaga ma wartość false, albo n+1, jeśli ustawione są wszystkie flagi.

W pierwszym przykładzie n = 6: flagi dla 1, 2, 3 i 5 zostają ustawione, -2 i 9 zostają pominięte, a pierwszą nieustawioną flagą jest 4. Dwa przebiegi liniowe zapewniają czas O(n), a flagi zajmują O(n) pamięci.

Algorytm

Utwórz present, czyli n+1 flag ustawionych na false.
Dla każdej wartości v w nums, dla której 1 ≤ v ≤ n, ustaw present[v] na true.
Zwróć pierwsze v od 1 do n, którego flaga ma wartość false.
Jeśli nie ma takiego, zwróć 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

Umieść każdą wartość w osobnym polu

Intuicja

Wartość v powinna znajdować się pod indeksem v-1. Gdy każda wartość od 1 do n znajduje się na swoim miejscu, pierwszy indeks i, pod którym nie ma wartości i+1, wskazuje odpowiedź.

Pod każdym indeksem zamień wartość na jej miejsce, jeśli mieści się w zakresie od 1 do n, a jej miejsce jeszcze jej nie zawiera. Wartość, która wraca na dany indeks, również może wymagać przeniesienia. Sprawdzanie miejsca docelowego, a nie indeksu i, zapobiega problemom z duplikatami: w [1, 1] druga 1 widzi 1 pod indeksem 0 i pozostaje na miejscu.

W pierwszym przykładzie indeks 0 odsyła 5 na właściwe miejsce, a następnie wartość 2, która wraca; później 1 i 3 trafiają na swoje miejsca, pozostawiając [1, 2, 3, -2, 5, 9]: indeks 3 to pierwsze niewłaściwe miejsce, więc odpowiedź to 4.

Każda zamiana umieszcza jedną wartość na właściwym miejscu na stałe, więc pętle wewnętrzne wykonują łącznie najwyżej n zamian: czas O(n) i pamięć O(1), z wyjątkiem R, które tworzy kopię modyfikowanego wektora.

Algorytm

Dla każdego indeksu i od 0 do n-1:
Dopóki 1 ≤ nums[i] ≤ n i nums[nums[i]-1] ≠ nums[i], zamień nums[i] z nums[nums[i]-1].
Po przejściu rozmieszczającym znajdź pierwszy indeks i, dla którego nums[i] ≠ i+1, i zwróć i+1.
Jeśli każde miejsce zawiera własną wartość, zwróć 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

Pułapki i przypadki brzegowe

Przerywanie zamian, gdy nums[i] == i+1, zamiast wtedy, gdy właściwa pozycja zawiera już daną wartość. W przypadku [1, 1] obie jedynki będą zamieniane bez końca.
Użycie if zamiast while do zamiany. W pierwszym przykładzie 2, które wraca z indeksu 4, nigdy nie trafia na indeks 1, więc zwracasz 2 zamiast 4.
Przypisanie nums[i] = nums[nums[i]-1], a następnie ponowne indeksowanie za pomocą nums[i], przez co odczytujesz indeks właściwej pozycji po jego zmianie. Najpierw zapisz indeks właściwej pozycji.
Pominięcie sprawdzenia zakresu, przez co 0, -2 lub 10^9 wskazuje indeks poza tablicą.
Zwrócenie n, gdy wszystkie pozycje są prawidłowe. Dla [4, 2, 1, 3] odpowiedzią jest 5.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu First Missing Positive?

Rozwiązanie polegające na rozmieszczaniu działa w czasie O(n) i wymaga O(1) dodatkowej przestrzeni. Pętla while znajduje się wewnątrz pętli for, ale każda zamiana umieszcza wartość na jej końcowym indeksie, więc cały przebieg wykonuje najwyżej n zamian. Wersja z tablicą flag działa w czasie O(n) i wymaga O(n) pamięci, a skanowanie w poszukiwaniu każdego kandydata ma złożoność O(n²).

Dlaczego odpowiedź nigdy nie jest większa niż n+1?

Liczby od 1 do n+1 to n+1 różnych wartości, a tablica o długości n zawiera najwyżej n różnych wartości, więc brakuje jednej z nich. Odpowiedzią jest n+1 dokładnie wtedy, gdy tablica zawiera każdą wartość od 1 do n.

Czy rozwiązanie modyfikujące tablicę w miejscu zmienia tablicę wejściową?

Tak, zmienia kolejność wartości. Jeśli wywołujący potrzebuje pierwotnej kolejności, najpierw skopiuj tablicę, co zwiększa dodatkowe zużycie pamięci z powrotem do O(n). Inna metoda działająca w miejscu zastępuje każdą wartość spoza zakresu od 1 do n wartością n+1, a następnie oznacza, że v występuje, ustawiając nums[v-1] jako ujemne; ona również zmienia tablicę.

def firstMissingPositive(nums):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argument

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

Oczekiwany wynik

First Missing Positive

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Wypróbuj każdego kandydata, wykonując pełne skanowanie

Oznacz wartości od 1 do n w tablicy flag

Umieść każdą wartość w osobnym polu

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania