Contains Duplicate
Otrzymujesz tablicę liczb całkowitych nums. Zwróć true, jeśli jakaś wartość występuje w niej co najmniej dwa razy, a false, jeśli wszystkie wartości są różne.
Funkcja
- numsinteger-array
- liczby całkowite do sprawdzenia
- Zwracaboolean
- true, jeśli jakaś wartość pojawia się co najmniej dwa razy, false w przeciwnym razie
Ograniczenia
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109
Przykłady
- Wejście
- nums = [3, 1, 4, 1, 5]
- Wyjście
- true
- Wyjaśnienie
- Wartość
1występuje pod indeksem 1 i ponownie pod indeksem 3, więc odpowiedź totrue.
- Wejście
- nums = [2, 7, 1, 8]
- Wyjście
- false
- Wyjaśnienie
2,7,1i8to cztery różne wartości, więc nic się nie powtarza.
- Wejście
- nums = [-4, 4, 0]
- Wyjście
- false
- Wyjaśnienie
-4i4mają tę samą wartość bezwzględną, ale są różnymi liczbami, a0występuje raz, więc odpowiedź tofalse.
Pytanie dodatkowe
Czy możesz zatrzymać się, gdy tylko napotkasz pierwszą powtarzającą się wartość, zamiast zawsze odczytywać całą tablicę?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Porównywanie każdej wartości z każdą inną działa, ale dla
10^4wartości oznacza to około5 × 10^7porównań. Co możesz zapamiętać o wartościach, które już minąłeś?Powtórzenie oznacza, że bieżąca wartość to taka, którą już napotkałeś. Zbiór haszujący odpowiada na pytanie „czy napotkałem już tę wartość?” w średnim czasie stałym.
Przejdź raz przez tablicę, używając pustego zbioru. Dla każdej wartości zwróć
true, jeśli już znajduje się w zbiorze; w przeciwnym razie dodaj ją. Jeśli pętla się zakończy, wszystkie wartości były różne.
Rozwiązanie
Powtórzenie to wartość, z którą już się spotkałeś, a zadanie polega na szybkim ustaleniu: „czy już się z tym spotkałem?”. Porównanie każdej pary daje odpowiedź, ale dla n = 10^4 oznacza to n(n-1)/2, czyli około 5 × 10^7 porównań. Sortowanie umieszcza równe wartości obok siebie, a zbiór mieszający odpowiada na to pytanie średnio w czasie O(1), co pozwala wykonać jedno przejście.
Posortuj, a następnie porównaj sąsiadujące elementy
Intuicja
W posortowanej tablicy równe wartości znajdują się obok siebie. [3, 1, 4, 1, 5] po posortowaniu daje [1, 1, 3, 4, 5], a dwie wartości 1 stykają się ze sobą. Dlatego po posortowaniu porównujesz każdą wartość tylko z tą, która znajduje się bezpośrednio przed nią: n-1 porównań zamiast n(n-1)/2, których wymaga sprawdzenie każdej pary.
Jeśli żadne dwa sąsiednie elementy nie są równe, to żadne dwie wartości w całej tablicy nie są równe: każda wartość znajdująca się między dwiema kopiami x w posortowanym porządku musiałaby być jednocześnie co najmniej równa x i co najwyżej równa x, a więc sama musiałaby być kolejnym x.
Największy wpływ na złożoność czasową ma sortowanie: O(n log n). Posortowanie nums w miejscu nie wymaga dodatkowej tablicy, ale zmienia kolejność danych wejściowych przekazanych przez wywołującego; jeśli jest to niedozwolone, posortuj kopię, co wymaga O(n) pamięci.
Algorytm
- Posortuj
numsrosnąco. - Wykonuj pętlę dla
iod 1 do ostatniego indeksu. - Jeśli
nums[i]jest równenums[i-1], zwróćtrue. - Po pętli zwróć
false.
def containsDuplicate(nums):
nums.sort()
# After sorting, equal values sit next to each other.
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
return True
return FalseJedno przejście z użyciem zbioru mieszającego
Intuicja
Przejdź raz przez tablicę i zapisuj każdą napotkaną wartość w zbiorze haszującym. Zanim dodasz wartość, sprawdź, czy już znajduje się w zbiorze. Dla [3, 1, 4, 1, 5] zbiór rozrasta się do {3, 1, 4}, a gdy pojawia się druga 1, zbiór już ją zawiera, więc zwracasz true bez odczytywania 5.
Zbiór zawsze zawiera dokładnie wartości znajdujące się przed bieżącą pozycją, więc trafienie oznacza, że bieżąca wartość pojawiła się wcześniej, a dotarcie do końca bez trafienia oznacza, że wszystkie wartości są różne.
Wyszukiwanie w zbiorze haszującym i dodawanie do niego zajmują średnio O(1) czasu, więc całe przejście ma złożoność O(n). Ceną jest pamięć: jeśli nie ma powtórzeń, zbiór ostatecznie zawiera wszystkie n wartości.
Algorytm
- Utwórz pusty zbiór haszujący
seen. - Dla każdej wartości w
nums, jeśli znajduje się ona wseen, zwróćtrue. - W przeciwnym razie dodaj ją do
seen. - Po pętli zwróć
false.
def containsDuplicate(nums):
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False
Pułapki i przypadki brzegowe
Logika jest krótka, więc błędy wynikają z granic pętli i tego, co porównujesz.
- Porównywanie każdej pary z wewnętrzną pętlą zaczynającą się od
j = i. Każda wartość pasuje wtedy do samej siebie, a wynikiem jest zawszetrue. - Porównywanie sąsiadów bez wcześniejszego sortowania. W
[9, 1, 2, 3, 9]dwie wartości9nie sąsiadują ze sobą. - Rozpoczynanie pętli po sąsiadach od indeksu 0 i odczytywanie
nums[-1]. Zacznij od 1 — tablica z jedną wartością prawidłowo zwrócifalse. - Uznawanie wartości o takim samym module za równe, na przykład przez haszowanie
abs(x).-4i4to różne liczby. - Zapisywanie komparatora sortowania w C, który zwraca
x - y. Różnica mieści się tutaj w zakresie±2 × 10^9, poniżej limituintwynoszącego2^31-1 = 2147483647, więc akurat się mieści; przy wartościach bliskich limitom typuintwystąpi przepełnienie i sortowanie da błędny wynik. Zamiast tego zwracaj(x > y) - (x < y).
Najczęstsze pytania3
Jaka jest złożoność czasowa zadania „Contains Duplicate”?
Rozwiązanie z użyciem zbioru haszującego działa średnio w czasie O(n) i wykorzystuje O(n) dodatkowej pamięci. Wstępne sortowanie zajmuje O(n log n) czasu i nie wymaga dodatkowej tablicy, jeśli możesz zmienić kolejność elementów wejściowych. Porównywanie każdej pary zajmuje O(n²) czasu.
Czy potrafisz rozwiązać zadanie „Contains Duplicate” bez dodatkowej pamięci?
Tak, jeśli możesz zmienić kolejność elementów tablicy: posortuj ją w miejscu i porównaj każdą wartość z sąsiednią. W ten sposób zamieniasz zbiór o złożoności O(n) na czas działania O(n log n). Bez zmiany kolejności i bez dodatkowej pamięci pozostaje tylko sprawdzanie par o złożoności O(n²).
Dlaczego zbiór haszujący przyspiesza sprawdzanie?
Zbiór haszujący przechowuje wartości na podstawie ich skrótów, więc sprawdzenie, czy zawiera daną wartość, zajmuje średnio stały czas zamiast wymagać przeszukiwania. Każdy element wymaga jednego wyszukania i jednego wstawienia, dzięki czemu całe przejście ma złożoność liniową.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def containsDuplicate(nums):
# Napisz kod tutajTest #1
Test #2
Test #3
Argument
nums = [3, 1, 4, 1, 5]
Oczekiwany wynik
true