Second Largest Number
Otrzymujesz listę liczb całkowitych nums. Zwróć jej drugą co do wielkości różną wartość: największą wartość, która jest ściśle mniejsza od maksimum. Wartości mogą się powtarzać, więc dla [5, 5, 3] odpowiedzią jest 3, a nie 5. Lista zawsze zawiera co najmniej dwie różne wartości.
Funkcja
- numsinteger-array
- lista liczb całkowitych zawierająca co najmniej dwie różne wartości
- Zwracainteger
- największa wartość mniejsza od maksimum
Ograniczenia
2 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109numszawiera co najmniej dwie różne wartości.
Przykłady
- Wejście
- nums = [4, 9, 2, 7, 9]
- Wyjście
- 7
- Wyjaśnienie
- Maksimum to
9. Występuje dwa razy, ale druga kopia maksimum się nie liczy, więc odpowiedzią jest kolejna niższa wartość,7.
- Wejście
- nums = [-5, -1, -8]
- Wyjście
- -5
- Wyjaśnienie
- Od największej do najmniejszej wartości to
-1,-5,-8. Druga co do wielkości to-5, mimo że jest ujemna.
- Wejście
- nums = [6, 6, 6, 3]
- Wyjście
- 3
- Wyjaśnienie
- Istnieją tylko dwie różne wartości:
6i3. Niezależnie od tego, ile razy powtarza się6, druga co do wielkości wartość to3.
Pytanie dodatkowe
Czy potrafisz zwrócić trzecią największą różną wartość w jednym przebiegu, używając trzech zmiennych i bez sortowania?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Znalezienie maksimum wymaga jednej zmiennej. Co pozwoliłaby Ci zapamiętać druga zmienna podczas czytania listy?
Śledź największą i drugą co do wielkości różną wartość. Nowa wartość może być większa od największej, znaleźć się ściśle między tymi dwiema wartościami albo niczego nie zmienić.
Ustaw obie poniższe zmienne na dowolną dozwoloną wartość. Jeśli
x > largest, przenieślargestdosecondi zapiszx. W przeciwnym razie, jeślixjest ściśle między nimi, zapisz je wsecond.
Rozwiązanie
Dwie kwestie sprawiają, że jest to trudniejsze niż znalezienie maksimum. Maksimum może się powtarzać, a powtórzenia nie wolno podawać jako drugiej największej wartości. Odpowiedź może być ujemna, więc zmienna zaczynająca od 0 daje błędny wynik dla listy zawierającej wyłącznie liczby ujemne. Śledzenie dwóch największych różnych wartości w jednym przebiegu, przy użyciu ścisłych porównań, rozwiązuje oba problemy.
Sortuj i zejdź w dół poniżej maksimum
Intuicja
Posortuj kopię od najmniejszej do największej wartości. Maksymalna wartość znajduje się na końcu, być może powtórzona kilka razy z rzędu. Przesuwaj się w lewo od końca, mijając każde wystąpienie maksimum; pierwsza inna wartość to druga co do wielkości. Dla [6, 6, 6, 3] posortowana kopia to [3, 6, 6, 6]: pomijasz trzy 6 i trafiasz na 3.
Zwrócenie przedostatniego elementu to klasyczny błąd w tym przypadku. Dla [4, 9, 2, 7, 9] zwraca 9, czyli ponownie maksimum. Przeszukiwanie nie może wyjść poza początek listy, ponieważ zawiera ona co najmniej dwie różne wartości.
Odpowiedź jest poprawna, ale sortowanie porządkuje wszystkie wartości, choć interesują Cię tylko dwie największe. Zajmuje O(n log n) czasu, a kopia O(n) pamięci.
Algorytm
- Skopiuj
numsi posortuj kopię od najmniejszej do największej wartości. - Ustaw indeks
ina ostatniej pozycji. - Gdy wartość pod indeksem
ijest równa maksimum, przesuńio jedną pozycję w lewo. - Zwróć wartość pod indeksem
i.
def secondLargest(nums):
ordered = sorted(nums)
i = len(ordered) - 1
# Step left past every copy of the maximum.
while ordered[i] == ordered[-1]:
i -= 1
return ordered[i]Dwa przebiegi
Intuicja
Podziel zadanie na dwa przebiegi. W pierwszym znajdź maksimum, tak jak w zadaniu Znajdź największą liczbę. W drugim poszukaj największej wartości, która jest ściśle mniejsza od tego maksimum. Dla [4, 9, 2, 7, 9] pierwszy przebieg znajduje 9, a drugi pomija obie wartości 9 i zachowuje największą z wartości 4, 2 i 7, czyli 7.
Ustaw second na wartość mniejszą od każdej wartości, jaką może zawierać lista, na przykład na najmniejszą liczbę całkowitą obsługiwaną przez twój język. Lista zawiera co najmniej dwie różne wartości, więc jakaś wartość jest mniejsza od maksimum i zawsze zastąpi tę początkową wartość.
Każdy przebieg znajduje bieżące maksimum, więc łączna złożoność wynosi O(n) czasowo i O(1) pamięciowo. Kosztem jest dwukrotne odczytanie listy, co jest niemożliwe, gdy wartości napływają pojedynczo i znikają po ich odczytaniu.
Algorytm
- Przejdź raz przez
numsi zapisz największą wartość wlargest. - Ustaw
secondna wartość mniejszą niż każda dozwolona wartość. - Przejdź ponownie. Dla każdego
x, dla któregox < largestix > second, ustawsecondnax. - Zwróć
second.
def secondLargest(nums):
largest = nums[0]
for x in nums:
if x > largest:
largest = x
second = float("-inf") # below every allowed value
for x in nums:
if x < largest and x > second:
second = x
return secondJedno przejście śledzące dwa największe
Intuicja
Zachowuj dwie zmienne, largest i second, przechowujące dwie największe różne wartości napotkane do tej pory. Każda nowa wartość x pasuje do jednego z trzech przypadków. Jeśli x jest większe niż largest, dotychczasowe largest spada na drugie miejsce, a x zajmuje pierwsze. Jeśli x leży ściśle między second a largest, staje się nowym second. W każdym innym przypadku nic się nie zmienia.
To ścisłe porównania obsługują duplikaty. Dla [4, 9, 2, 7, 9]: largest przyjmuje wartość 4, a następnie 9, przy czym second = 4. 2 niczego nie zmienia, 7 leży między 4 a 9, więc second = 7, a ostatnie 9 jest równe largest, więc zostaje pominięte. Odpowiedź to 7.
Ustaw obie zmienne na wartości mniejsze od każdej możliwej wartości. Ustawienie obu na 0 zwraca 0 dla [-5, -1, -8], ponieważ żadna wartość nigdy nie jest większa od 0. Ponieważ lista zawiera dwie różne wartości, second zawsze ostatecznie przyjmuje rzeczywistą wartość z listy.
Algorytm
- Ustaw
largestisecondponiżej każdej dozwolonej wartości. - Przejdź pętlą przez każdą wartość
xwnums. - Jeśli
x > largest, przenieślargestdosecondi ustawlargestnax. - W przeciwnym razie, jeśli
x < largestix > second, ustawsecondnax. - Po pętli zwróć
second.
def secondLargest(nums):
# Both start below every allowed value.
largest = second = float("-inf")
for x in nums:
if x > largest:
second = largest # the old maximum drops to second place
largest = x
elif largest > x > second:
second = x
return second
Pułapki i przypadki brzegowe
Większość błędnych odpowiedzi wynika z powtórzeń maksimum lub wartości ujemnych.
- Zwracanie przedostatniego elementu posortowanej listy. Jeśli maksimum się powtarza, jak w przypadku
[4, 9, 2, 7, 9], ponownie jest to maksimum. - Ustawianie zmiennych na
0. W przypadku[-5, -1, -8]żadna wartość nie jest większa niż0, więc zwracasz0, liczbę, której nie ma na liście. - Zapisywanie
x >= largestw pierwszym przypadku. Drugie9przenosi wtedy pierwsze9dosecond, a ty zwracasz9. - Aktualizowanie
secondtylko wtedy, gdy pojawia się nowe maksimum. W przypadku[10, 20, 15]wartość15nigdy nie trafia dosecond, a ty zwracasz10. - Usuwanie duplikatów za pomocą zbioru, a następnie sortowanie. To działa, ale wymaga
O(n)pamięci iO(n log n)czasu, choć wystarczy jedno przejście.
Najczęstsze pytania3
Jak znaleźć drugą co do wielkości liczbę w tablicy w jednym przebiegu?
Przechowuj największą i drugą co do wielkości różną wartość napotkaną do tej pory. Gdy wartość jest większa od największej, dotychczasowa największa staje się drugą co do wielkości. Gdy wartość leży ściśle między nimi, zastępuje drugą. Po jednym przejściu zmienna second zawiera odpowiedź.
Jaka jest złożoność czasowa znajdowania drugiego największego elementu?
Metody jedno- i dw przebiegowe mają złożoność czasową O(n) i wymagają dodatkowej pamięci O(1). Wstępne sortowanie zajmuje O(n log n) czasu. Nie da się osiągnąć lepszej złożoności niż O(n), ponieważ każdą wartość trzeba odczytać co najmniej raz.
Jak duplikaty wpływają na drugi co do wielkości element?
Ten problem wymaga podania drugiej największej różnej wartości, więc pomija się kopie maksimum. Dla [9, 9, 7] odpowiedzią jest 7. Niektóre wersje pytania uwzględniają zamiast tego pozycje i wtedy odpowiedzią byłoby 9, więc przed napisaniem kodu sprawdź, o którą wersję chodzi.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def secondLargest(nums):
# Napisz tutaj kodTest #1
Test #2
Test #3
Argument
nums = [4, 9, 2, 7, 9]
Oczekiwany wynik
7