Missing Number

Q: Jaka jest złożoność czasowa problemu brakującej liczby?

Rozwiązania wykorzystujące sumę i XOR działają w czasie O(n) i wymagają O(1) dodatkowej pamięci, ponieważ odczytują każdą wartość raz i przechowują jedną liczbę. Wyszukiwanie na liście każdego kandydata zajmuje O(n²) . Wcześniejsze sortowanie i szukanie luki zajmuje O(n log n) .

ŁatweOperacje na bitach Matematyka i symulacja

+10

Otrzymujesz listę nums zawierającą n różnych liczb całkowitych, z których każda mieści się w przedziale od 0 do n. Zakres od 0 do n obejmuje n+1 liczb, więc dokładnie jednej z nich brakuje na liście. Zwróć tę brakującą liczbę.

Funkcja

missingNumber(nums: integer-array) → integer

numsinteger-array: n różnych liczb całkowitych z zakresu od 0 do n, w dowolnej kolejności
Zwracainteger: jedyna liczba z zakresu od 0 do n, której nie ma w nums

Ograniczenia

n == nums.length
1 ≤ n ≤ 10⁴
0 ≤ nums[i] ≤ n
Wszystkie wartości w nums są różne.

Przykłady

Wejście: nums = [4, 2, 0, 1]
Wyjście: 3
Wyjaśnienie: Lista ma 4 wartości, więc zakres wynosi od 0 do 4. Zawiera 0, 1, 2 i 4, a 3 to jedyna liczba, która nie ma dopasowania.

+13 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy gdyby lista była posortowana, udałoby Ci się znaleźć brakującą liczbę w czasie O(log n) za pomocą wyszukiwania binarnego?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Wiesz dokładnie, co powinna zawierać lista: każdą liczbę całkowitą od 0 do n. Wyszukiwanie kolejno każdej z tych liczb działa, ale wymaga pełnego przeszukiwania dla każdej liczby. Zamiast tego sprowadź cały zakres i listę do jednej wartości podsumowującej każdą z nich — sumy lub XOR — a różnica między nimi to brakująca liczba. Wymaga to jednego przejścia i nie zużywa dodatkowej pamięci.

Sprawdź każdego kandydata

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

Intuicja

Odpowiedzią jest jedna z n+1 liczb od 0 do n. Sprawdzaj je po kolei i przeszukuj listę w poszukiwaniu każdej z nich. Pierwszy kandydat, któremu nie odpowiada żadna wartość, jest brakującą liczbą.

To poprawne, ponieważ każda liczba z tego zakresu albo znajduje się na liście, albo jest odpowiedzią, a lista nie zawiera duplikatów, więc dokładnie jeden kandydat nie zostanie znaleziony.

To powolne rozwiązanie, ponieważ sprawdzenie każdego kandydata wymaga przeskanowania maksymalnie n wartości. Gdy luka znajduje się blisko końca, przeszukiwany jest niemal każdy kandydat: dla n = 10^4 i luki blisko końca daje to około 5 × 10^7 porównań. Podwojenie listy zwiększa nakład pracy czterokrotnie.

Algorytm

Iteruj po candidate od 0 do n włącznie.
Przeszukaj nums w poszukiwaniu wartości równej candidate.
Jeśli znajdziesz ją podczas przeszukiwania, przejdź do następnego kandydata.
Jeśli przeszukiwanie zakończy się bez dopasowania, zwróć 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

Odejmij sumę od oczekiwanej sumy

Intuicja

Gdyby niczego nie brakowało, lista zawierałaby każdą liczbę od 0 do n, a ich suma wynosiłaby n(n+1)/2. Rzeczywista lista to ten pełny zestaw z usuniętą jedną liczbą, więc jej suma jest mniejsza dokładnie o tę liczbę.

Dla [4, 2, 0, 1] n wynosi 4, a suma pełnego zakresu to 4 × 5 / 2 = 10. Suma liczb na liście wynosi 7, a 10 minus 7 daje 3.

Jedno przejście sumuje elementy listy, więc złożoność czasowa wynosi O(n), a Ty przechowujesz jedną bieżącą sumę. W tym przypadku pełna suma wynosi co najwyżej około 5 × 10^7, co mieści się w 32-bitowej liczbie całkowitej. Dla znacznie większych wartości n wynik obliczenia wzoru przekracza zakres 32-bitowej liczby całkowitej, dlatego wersje w Java, C, C++, C# i Rust wykonują obliczenia na 64 bitach.

Algorytm

Niech n oznacza długość nums.
Oblicz pełną sumę n(n+1)/2.
Dodaj do siebie wszystkie wartości w nums.
Zwróć pełną sumę pomniejszoną o sumę elementów listy.

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

XOR indeksów z wartościami

Intuicja

XOR anuluje pary. a ^ a to 0, a ^ 0 to a, a kolejność operacji nie ma znaczenia. Jeśli więc wykonasz XOR na zbiorze liczb, w którym każda liczba występuje dwa razy, z wyjątkiem jednej wartości, pary się anulują i pozostanie ta jedna wartość.

Utwórz taki zbiór na podstawie treści zadania: indeksy od 0 do n oraz wartości z nums. Liczba znajdująca się na liście występuje raz jako indeks i raz jako wartość, więc się anuluje. Brakująca liczba występuje tylko jako indeks, więc pozostaje. Pętla odwiedza indeksy od 0 do n-1, więc rozpocznij od n, aby uwzględnić ostatni indeks.

Dla [4, 2, 0, 1]: zacznij od 4, a następnie wykonaj XOR z 0 i 4, 1 i 2, 2 i 0, 3 i 1. Czwórki, dwójki, jedynki i zera się anulują, a pozostanie 3. To jedno przejście z jedną bieżącą wartością, która w przeciwieństwie do sumy nigdy nie wykracza poza bity używane już przez n, więc nie może dojść do przepełnienia.

Algorytm

Ustaw result na n, czyli długość nums.
Dla każdego indeksu i wykonaj operację XOR na result z i oraz nums[i].
Zwróć 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

Pułapki i przypadki brzegowe

Większość błędnych odpowiedzi wynika z pomyłek na obu krańcach zakresu.

Zapomnienie, że brakujeć może samego n. W [0, 1, 2] odpowiedzią jest 3, która nie jest indeksem listy. Wersja z XOR musi zaczynać od n, a skanowanie posortowanej listy, które szuka pierwszego nums[i] != i, musi zwrócić n, gdy wszystkie pozycje są zgodne.
Użycie nieprawidłowego rozmiaru zakresu. Liczby biegną od 0 do n, czyli jest ich n+1, więc pełna suma wynosi n(n+1)/2, a nie (n-1)n/2.
Założenie, że 0 zawsze występuje. W [1] odpowiedzią jest 0, a kod, który zaczyna wyszukiwanie od 1, jej nie znajdzie.
Przepełnienie w wersji z sumą. Przy arytmetyce 32-bitowej iloczyn n(n+1) ulega przepełnieniu, gdy n przekroczy około 46 000, zanim dzielenie przez 2 zdąży pomóc, a samo n(n+1)/2 przestaje mieścić się w zakresie w pobliżu 65 000. Użyj arytmetyki 64-bitowej albo XOR.

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu brakującej liczby?

Rozwiązania wykorzystujące sumę i XOR działają w czasie O(n) i wymagają O(1) dodatkowej pamięci, ponieważ odczytują każdą wartość raz i przechowują jedną liczbę. Wyszukiwanie na liście każdego kandydata zajmuje O(n²). Wcześniejsze sortowanie i szukanie luki zajmuje O(n log n).

Dlaczego XOR znajduje brakującą liczbę?

Operacja XOR liczby z samą sobą daje 0, XOR z 0 niczego nie zmienia, a kolejność nie ma znaczenia. Gdy wykonasz operację XOR na wszystkich indeksach od 0 do n oraz wszystkich wartościach, każda liczba znajdująca się na liście pojawia się dwa razy i się znosi. Brakująca liczba pojawia się tylko raz, jako indeks, więc jest wynikiem.

Czy użyć wzoru na sumę, czy operatora XOR?

Oba wymagają jednego przejścia i stałej ilości pamięci. Sumę łatwiej wyjaśnić, ale w arytmetyce 32-bitowej iloczyn n(n+1) przepełnia się, gdy n przekracza około 46 000, więc potrzebujesz arytmetyki 64-bitowej. XOR nigdy się nie przepełnia. W Pythonie, Ruby i innych językach z nieograniczonymi liczbami całkowitymi ta różnica znika.

Czy potrafisz rozwiązać zadanie „Brakująca liczba” za pomocą zbioru mieszającego?

Tak. Umieść każdą wartość w zbiorze, a następnie sprawdzaj liczby od 0 do n i zwróć pierwszą, której brakuje w zbiorze. Działa to w czasie O(n), ale wymaga dodatkowej pamięci O(n), której nie potrzebują metody sumy i XOR.

Python

def missingNumber(nums):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

nums = [4, 2, 0, 1]

Oczekiwane

Missing Number

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Sprawdź każdego kandydata

Odejmij sumę od oczekiwanej sumy

XOR indeksów z wartościami

Pułapki i przypadki brzegowe

Najczęstsze pytania4

Podobne zadania