Intersection of Two Arrays
Otrzymujesz dwie tablice liczb całkowitych: nums1 i nums2. Zwróć każdą wartość, która występuje w obu tablicach, posortowaną rosnąco. Każda wspólna wartość pojawia się w odpowiedzi raz, niezależnie od tego, ile razy się powtarza w którejkolwiek z tablic.
Funkcja
- nums1integer-array
- pierwsza lista liczb całkowitych
- nums2integer-array
- druga lista liczb całkowitych
- Zwracainteger-array
- wartości występujące na obu listach, każda po jednym razie, w kolejności rosnącej
Ograniczenia
1 ≤ nums1.length, nums2.length ≤ 5000-105 ≤ nums1[i], nums2[i] ≤ 105- Co najmniej jedna wartość występuje w obu tablicach.
Przykłady
- Wejście
- nums1 = [6, 2, 9, 2, 4]nums2 = [4, 4, 1, 6]
- Wyjście
- [4, 6]
- Wyjaśnienie
4i6znajdują się w obu tablicach.4występuje dwa razy wnums2, ale jest wymienione raz, a2i9nigdy nie występują wnums2.
- Wejście
- nums1 = [-3, 0, 7]nums2 = [7, -3, -3, 5]
- Wyjście
- [-3, 7]
- Wyjaśnienie
-3i7znajdują się w obu tablicach. W kolejności rosnącej najpierw występuje-3, mimo że wnums2najpierw występuje7.
+16 ukrytych testów przy wysłaniu
Pytanie dodatkowe
Co jeśli nums1 zawiera 10 wartości, a nums2 milion, i jest już posortowana? Które podejście byś wybrał i czy wyszukiwanie binarne może być szybsze niż pełne przejście?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Dla każdej wartości w
nums1możesz przeszukać całenums2. Przy 5000 wartościach w każdej tablicy oznacza to nawet2.5 × 10^7porównań. Jakie pytanie zadajesz w kółko?Powtarzające się pytanie brzmi: „czy ta wartość znajduje się w drugiej tablicy?”. Zbiór haszujący utworzony na podstawie jednej tablicy odpowiada na nie średnio w czasie stałym.
Utwórz zbiór z
nums1. Przejdź przeznums2; gdy wartość znajduje się w zbiorze, dodaj ją do wyniku i usuń ją ze zbioru, aby jej późniejsza kopia nie mogła zostać dodana ponownie. Posortuj wynik przed jego zwróceniem.
Rozwiązanie
O tym problemie decydują dwa szczegóły: wartość, która powtarza się po obu stronach, nadal trafia do odpowiedzi tylko raz, a odpowiedź musi być posortowana. Porównanie każdej pary działa, ale wymaga n × m porównań, czyli 2.5 × 10^7, gdy obie tablice zawierają po 5000 wartości. Posortowanie obu tablic pozwala dwóm wskaźnikom znaleźć wspólne wartości w odpowiedniej kolejności, a zbiór haszujący jednej tablicy pozwala w stałym czasie sprawdzić, „czy ta wartość znajduje się w nums1?”.
Porównaj każdą parę
Poprawne, ale nie kończy się na największych testach
Intuicja
Sprawdź każdą wartość z nums1 w nums2. Zakończ sprawdzanie przy pierwszym dopasowaniu i pomiń wartość, która już znajduje się w odpowiedzi, więc dla [8, 8, 8, 8] i [8, 8] wynikiem będzie jedno 8, a nie cztery. Na końcu posortuj odpowiedź.
To rozwiązanie jest poprawne, ponieważ wartość trafia do odpowiedzi dokładnie wtedy, gdy któraś jej kopia w nums1 znajduje dopasowanie w nums2, a pomijanie zapobiega dodaniu jej po raz drugi.
Jest powolne, ponieważ każda wartość z nums1 może wymagać sprawdzenia całego nums2. Przy 5000 wartościach w każdej tablicy oznacza to do 2.5 × 10^7 porównań, a w dużych testach większość wartości nie znajduje dopasowania, więc większość sprawdzeń trwa aż do końca.
Algorytm
- Zacznij od pustej listy odpowiedzi.
- Dla każdej wartości
awnums1pomiń ją, jeśli znajduje się już na liście odpowiedzi. - W przeciwnym razie przeszukaj
nums2; przy pierwszej wartości równejadodajado listy odpowiedzi i zakończ przeszukiwanie. - Posortuj odpowiedź rosnąco i ją zwróć.
def intersection(nums1, nums2):
result = []
for a in nums1:
if a in result:
continue
# Look for a anywhere in nums2.
for b in nums2:
if a == b:
result.append(a)
break
result.sort()
return resultPosortuj obie tablice, a następnie przejdź przez nie za pomocą dwóch wskaźników
Intuicja
Po posortowaniu przykład 1 przyjmuje postać [2, 2, 4, 6, 9] i [1, 4, 4, 6]. Umieść wskaźnik i na początku pierwszej tablicy, a j na początku drugiej. Wskaźnik przy mniejszej wartości przesuwa się do przodu: ta wartość nie może już pasować do żadnej dalszej wartości w drugiej tablicy, w której każda wartość jest co najmniej tak duża. Gdy oba wskaźniki wskazują tę samą wartość, jest ona wspólna, więc dodaj ją i przesuń oba wskaźniki.
W przykładzie: 2 > 1 przesuwa j, oba 2 są mniejsze od 4 i przesuwają i, 4 = 4 dodaje 4, drugie 4 jest mniejsze od 6 i przesuwa j, a 6 = 6 dodaje 6. Wartość występująca kilka razy po obu stronach, taka jak 2 w [2, 2, 3] i [2, 2], pasuje więcej niż raz; porównanie jej z ostatnią dodaną wartością pozwala zachować jedną kopię. Wynik jest posortowany bez żadnego dodatkowego kroku.
Sortowanie kosztuje O(n log n + m log m), a przejście O(n + m), ponieważ każdy krok przesuwa co najmniej jeden wskaźnik. Większość wersji sortuje kopie, co wymaga O(n + m) pamięci. Jeśli możesz zmienić kolejność danych wejściowych, posortuj je w miejscu, tak jak robi to kod C, a jedyną dodatkową pamięcią będzie ta potrzebna na wynik.
Algorytm
- Posortuj obie tablice.
- Ustaw
i = 0ij = 0. - Gdy oba wskaźniki znajdują się w swoich tablicach, przesuwaj wskaźnik wskazujący mniejszą wartość.
- Przy równych wartościach dodaj tę wartość, chyba że jest równa ostatnio dodanej wartości, a następnie przesuń oba wskaźniki.
- Zwróć wynik.
def intersection(nums1, nums2):
a = sorted(nums1)
b = sorted(nums2)
i, j = 0, 0
result = []
while i < len(a) and j < len(b):
if a[i] < b[j]:
i += 1
elif a[i] > b[j]:
j += 1
else:
# A shared value: keep it once, even if it repeats.
if not result or result[-1] != a[i]:
result.append(a[i])
i += 1
j += 1
return resultZbiór haszujący pierwszej tablicy
Intuicja
Umieść każdą wartość z nums1 w zbiorze haszującym. W przykładzie 1 zbiór to {6, 2, 9, 4}: powtarzające się 2 scala się podczas dodawania. Następnie przejdź po nums2 i sprawdzaj każdą wartość w zbiorze w stałym czasie. Pierwsze 4 znajduje się w zbiorze, więc trafia do odpowiedzi. Drugie 4 nie może się tam znaleźć, dlatego usuwasz wartość ze zbioru w chwili dopasowania. 1 nie ma w zbiorze, a 6 jest, co daje [4, 6].
Usuwanie przy dopasowaniu sprawia, że każda wartość występuje tylko raz: po pierwszym dopasowaniu wartość znika ze zbioru, więc kolejne jej wystąpienia w nums2 niczego nie znajdą. Każda dodana wartość występuje w obu tablicach, a każda wspólna wartość zostaje dodana, gdy pojawi się jej pierwsze wystąpienie w nums2.
Budowanie zbioru i przejście zajmują średnio O(n + m). Odpowiedź jest tworzona w kolejności z nums2, więc na końcu posortuj ją; zawiera k ≤ min(n, m) wartości, co kosztuje O(k log k). C nie ma wbudowanego zbioru, dlatego kod w C używa tablicy flag indeksowanej przez value + 10^5, co działa, ponieważ wartości są ograniczone.
Algorytm
- Utwórz zbiór haszujący
firstznums1. - Dla każdej wartości w
nums2, jeśli znajduje się wfirst, dodaj ją do odpowiedzi i usuń ją zfirst. - Posortuj odpowiedź rosnąco.
- Zwróć ją.
def intersection(nums1, nums2):
first = set(nums1)
result = []
for num in nums2:
if num in first:
result.append(num)
# Remove it so a repeat in nums2 is not added twice.
first.remove(num)
result.sort()
return result
Pułapki i przypadki brzegowe
Większość błędnych odpowiedzi wynika z powtarzających się wartości oraz kolejności wyniku.
- Dodawanie wartości za każdym razem, gdy pasuje. Tablice
[2, 2, 3, 3, 3]i[3, 2, 2]mają dwie wspólne wartości, więc odpowiedzią jest[2, 3], a nie[3, 2, 2]. - Zwracanie wartości w kolejności, w jakiej je znaleziono. Przejście po zbiorze haszującym przebiega zgodnie z
nums2, więc[7, -3]nadal trzeba posortować do postaci[-3, 7]. - Sortowanie liczb jako tekstu.
sort()w JavaScript bez komparatora porównuje ciągi znaków, więc[100000, 99]pozostaje w tej kolejności. Przekaż(x, y) => x - y. - Używanie przecięcia zbiorów i zapominanie o kolejności.
set(nums1) & set(nums2)w Pythonie znajduje właściwe wartości w nieokreślonej kolejności; opakuj je wsorted. - Indeksowanie tablicy flag surową wartością.
-3nie jest prawidłowym indeksem; najpierw przesuń każdą wartość o10^5.
Najczęstsze pytania4
Jaka jest złożoność czasowa wyznaczania części wspólnej dwóch tablic?
W przypadku zbioru haszującego znalezienie wspólnych wartości zajmuje średnio O(n + m), a posortowanie k wartości odpowiedzi dodaje O(k log k); zbiór zajmuje O(n) pamięci. Posortowanie obu tablic i przejście po nich za pomocą dwóch wskaźników zajmuje O(n log n + m log m). Porównanie każdej pary zajmuje O(n × m).
Czy użyć zbioru haszującego, czy dwóch wskaźników?
Użyj zbioru haszującego, gdy tablice nie są posortowane i masz dostępne miejsce w pamięci: wymaga najmniej pracy. Użyj dwóch wskaźników, gdy obie tablice są już posortowane albo gdy pamięć jest ograniczona i możesz posortować je w miejscu. Przejście nie wymaga zbioru i tworzy uporządkowany wynik.
Jak zachować powtarzające się wartości w części wspólnej?
Jeśli wartość powinna pojawić się tyle razy, ile występuje w obu tablicach, tak aby [3, 1, 3, 3] i [3, 3] dawały [3, 3], zastąp zbiór mapą zliczającą. Zlicz wartości w nums1, a dla każdej wartości w nums2, której licznik jest większy od zera, dodaj ją i zmniejsz jej licznik. W przejściu z użyciem dwóch wskaźników usuń sprawdzanie ostatniej dodanej wartości.
Jak znaleźć część wspólną, gdy jedna tablica jest za duża, by zmieścić się w pamięci?
Zbuduj zbiór haszujący z tablicy, która się zmieści, a większą odczytuj partiami, sprawdzając każdą wartość względem zbioru i usuwając ją przy dopasowaniu. Zużycie pamięci pozostaje na poziomie rozmiaru mniejszej tablicy. Jeśli nie zmieści się żadna z tablic, posortuj obie na dysku i wykonaj przejście dwoma wskaźnikami po posortowanych plikach.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
Python
def intersection(nums1, nums2):
# Napisz kod tutajPrzypadek 1
Przypadek 2
Wejście
nums1 = [6, 2, 9, 2, 4] nums2 = [4, 4, 1, 6]
Oczekiwane
[4, 6]