Single Number
Otrzymujesz listę nums, w której każda wartość występuje dokładnie dwa razy, z wyjątkiem jednej wartości, która występuje tylko raz. Zwróć wartość, która występuje raz.
Funkcja
- numsinteger-array
- lista, w której każda wartość występuje dwa razy, z wyjątkiem jednej
- Zwracainteger
- wartość, która pojawia się tylko raz
Ograniczenia
1 ≤ nums.length < 104-104 ≤ nums[i] ≤ 104- Każda wartość pojawia się dokładnie dwa razy, z wyjątkiem jednej wartości, która pojawia się dokładnie raz.
Przykłady
- Wejście
- nums = [8, 3, 8]
- Wyjście
- 3
- Wyjaśnienie
- 8 pojawia się dwa razy, a 3 raz, więc odpowiedź to 3.
- Wejście
- nums = [5, -2, 7, 5, 7]
- Wyjście
- -2
- Wyjaśnienie
- 5 i 7 pojawiają się po dwa razy, a -2 to jedyna wartość, która występuje raz. Ujemną odpowiedź znajduje się tak samo jak dodatnią.
- Wejście
- nums = [42]
- Wyjście
- 42
- Wyjaśnienie
- Lista z jedną wartością nie ma żadnych par, więc ta wartość jest odpowiedzią.
+13 ukrytych testów przy wysłaniu
Pytanie dodatkowe
Co jeśli każda wartość pojawia się trzy razy, z wyjątkiem jednej? Samo XOR nie powoduje już skasowania się trójek. Czy nadal potrafisz znaleźć tę pojedynczą wartość w czasie O(n) i przy użyciu O(1) dodatkowej pamięci?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Gdyby każda para równych wartości mogła zniknąć, pozostałaby tylko odpowiedź. Czy istnieje operacja, która zamienia dwie równe liczby w nic?
XOR działa tak:
x ^ xto0, ax ^ 0tox. Kolejność nie ma też znaczenia, więc dwie kopie wartości nie muszą znajdować się obok siebie, aby się wzajemnie anulować.Zachowaj jedną zmienną, która zaczyna od
0. Wykonaj XOR na każdej wartości znums, a następnie ją zwróć. Nie jest potrzebna mapa ani sortowanie.
Rozwiązanie
Znalezienie wartości, która nie ma pary, to problem zliczania, a mapa haszująca zlicza każdą wartość w jednym przejściu. Problemem jest pamięć: mapa rośnie wraz z listą. XOR eliminuje potrzebę zliczania, ponieważ wynik operacji XOR wartości z samą sobą to 0. Wykonaj operację XOR na całej liście, a każda para się skasuje, pozostawiając pojedynczą wartość po jednym przejściu i przy użyciu jednej zmiennej.
Policz każdą wartość, skanując
Poprawne, ale nie kończy się na największych testach
Intuicja
Bierz kolejno każdą wartość i przeszukuj całą listę, aby policzyć, ile razy występuje. Wartość z pary liczy się 2 razy. Pojedyncza wartość liczy się 1 raz, więc zwróć pierwszą wartość, której licznik wynosi 1.
To poprawne rozwiązanie, ponieważ liczby wystąpień wynikają bezpośrednio z definicji odpowiedzi i nie wymaga ono dodatkowej pamięci poza licznikiem.
Jest powolne, ponieważ każda z n wartości powoduje pełne przeszukanie n wartości. Gdy pojedyncza wartość znajduje się na końcu listy zawierającej 9,999 elementów, oznacza to prawie 10^8 porównań.
Algorytm
- Przejdź pętlą przez każdą wartość w
nums. - Przeskanuj całą listę i policz wartości, które są jej równe.
- Jeśli licznik wynosi 1, zwróć tę wartość.
def singleNumber(nums):
for value in nums:
# count() scans the whole list: O(n) per value.
if nums.count(value) == 1:
return value
return 0Liczenie za pomocą mapy haszującej
Intuicja
Ponowne przeszukiwanie listy dla każdej wartości powtarza tę samą pracę. Zamiast tego zlicz wszystkie wartości za jednym razem: użyj mapy mieszającej, która przypisuje każdej wartości jej licznik; przy każdym kroku zwiększaj licznik bieżącej wartości o 1.
Dla [5, -2, 7, 5, 7] mapa zawiera na końcu: 5 → 2, -2 → 1, 7 → 2. Drugie przejście po mapie znajduje wpis z licznikiem równym 1, czyli -2.
Każda wartość wymaga jednej aktualizacji mapy, więc czas działania wynosi O(n). Mapa przechowuje około n/2 wpisów, co oznacza dodatkową pamięć rzędu O(n). W C, który nie ma wbudowanej mapy, tę samą rolę pełni tablica liczników indeksowana przez value + 10^4, ponieważ wartości są małe.
Algorytm
- Utwórz pustą mapę wartości do liczby wystąpień.
- Dla każdej wartości w
numszwiększ jej liczbę wystąpień o 1. - Przejdź przez mapę i zwróć wartość, której liczba wystąpień wynosi 1.
def singleNumber(nums):
counts = {}
for value in nums:
counts[value] = counts.get(value, 0) + 1
for value, count in counts.items():
if count == 1:
return value
return 0XOR wszystkie wartości
Intuicja
XOR porównuje dwie liczby bit po bicie i ustawia bit tam, gdzie się różnią. Wynikają z tego trzy fakty: x ^ x = 0, x ^ 0 = x i kolejność działań nie ma znaczenia.
Wykonaj więc XOR na całej liście, zapisując wynik w jednej zmiennej, która początkowo ma wartość 0. Możesz pogrupować działania tak, aby każda para spotkała swoją kopię, a każda para dała w wyniku 0. Pozostanie 0 ^ single, czyli pojedyncza wartość. Dla [8, 3, 8]: 0 ^ 8 = 8, potem 8 ^ 3 = 11, a następnie 11 ^ 8 = 3.
Liczby ujemne też działają. XOR operuje na bitach reprezentacji uzupełnień do dwóch, a dwie jednakowe liczby ujemne mają takie same bity, więc znoszą się tak jak każda inna para. Pętla odczytuje każdą wartość raz i używa jednej zmiennej: czas O(n) i dodatkowa pamięć O(1).
Algorytm
- Ustaw
resultna 0. - Dla każdej wartości w
numsustawresultnaresult ^ value. - Zwróć
result.
def singleNumber(nums):
result = 0
for value in nums:
result ^= value
return result
Pułapki i przypadki brzegowe
Pętla XOR jest krótka, więc błędy kryją się w tym, od czego się ją zaczyna, oraz w alternatywnych rozwiązaniach, po które sięgają ludzie.
- Ustawianie
resultnanums[0], a następnie przechodzenie w pętli po każdej wartości, łącznie z indeksem 0. Pierwsza wartość zostaje uwzględniona w operacji XOR dwukrotnie i się redukuje. Zacznij od 0 albo pomiń indeks 0. - Sortowanie i porównywanie sąsiednich elementów parami, a potem zapominanie, że pojedyncza wartość może być ostatnim elementem. W
[1, 1, 2]nie ma niedopasowanej pary, a odpowiedzią jest pozostała 2. - Używanie
2 × sum(distinct values) - sum(nums). Daje poprawną liczbę, ale zbiór unikatowych wartości wymagaO(n)pamięci, której unika wersja z XOR. - Zakładanie, że XOR działa również dla innych liczności. Redukuje wartości występujące parzystą liczbę razy. Jeśli jakaś wartość wystąpiłaby trzy razy, jedna kopia pozostałaby i zepsuła odpowiedź.
Najczęstsze pytania4
Jaka jest złożoność czasowa zadania Single Number?
Rozwiązanie XOR działa w czasie O(n) i wymaga O(1) dodatkowej przestrzeni, ponieważ odczytuje każdą wartość raz i przechowuje jedną zmienną. Mapa haszująca również działa w czasie O(n), ale wymaga O(n) pamięci. Zliczanie każdej wartości przez ponowne skanowanie zajmuje O(n²).
Dlaczego XOR rozwiązuje problem Single Number?
Wykonanie operacji XOR na liczbie i samej sobie daje 0, wykonanie operacji XOR z 0 niczego nie zmienia, a kolejność działań nie ma znaczenia. Dlatego gdy wykonujesz operację XOR na całej liście, każdą parę można połączyć, a jej wartości się znoszą do 0. Pozostaje tylko wartość bez pary.
Czy sztuczka z XOR działa w przypadku liczb ujemnych?
Tak. XOR działa na bitach, które przechowują liczbę, a liczby ujemne są przechowywane w kodzie uzupełnień do dwóch. Dwie równe liczby ujemne mają identyczne bity, więc znoszą się dokładnie tak samo jak liczby dodatnie. W [5, -2, 7, 5, 7] wynikiem jest -2.
Jak rozwiązać to, gdy pozostałe wartości pojawiają się trzy razy?
XOR usuwa pary, a nie trójki, więc w tym przypadku zawodzi. Zamiast tego policz, ile wartości ma ustawiony każdy z 32 bitów. Dla każdego bitu reszta z dzielenia tego wyniku przez 3 jest bitem pojedynczej wartości, ponieważ trójki dodają wielokrotności 3. Nadal działa to w czasie O(n), z dodatkową pamięcią O(1).
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
Python
def singleNumber(nums):
# Wpisz kod tutajPrzypadek 1
Przypadek 2
Przypadek 3
Wejście
nums = [8, 3, 8]
Oczekiwane
3