Second Largest Number

Q: 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.

PoczątkującyTablice i napisy

+10

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

secondLargest(nums: integer-array) → integer

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
-10⁹ ≤ nums[i] ≤ 10⁹
nums zawiera 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: 6 i 3. Niezależnie od tego, ile razy powtarza się 6, druga co do wielkości wartość to 3.

+15 ukrytych testów przy wysłaniu

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.

Otwarte: 0 z 3

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 nums i posortuj kopię od najmniejszej do największej wartości.
Ustaw indeks i na ostatniej pozycji.
Gdy wartość pod indeksem i jest równa maksimum, przesuń i o 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 nums i zapisz największą wartość w largest.
Ustaw second na wartość mniejszą niż każda dozwolona wartość.
Przejdź ponownie. Dla każdego x, dla którego x < largest i x > second, ustaw second na x.
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 second

Jedno 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 largest i second poniżej każdej dozwolonej wartości.
Przejdź pętlą przez każdą wartość x w nums.
Jeśli x > largest, przenieś largest do second i ustaw largest na x.
W przeciwnym razie, jeśli x < largest i x > second, ustaw second na x.
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 zwracasz 0, liczbę, której nie ma na liście.
Zapisywanie x >= largest w pierwszym przypadku. Drugie 9 przenosi wtedy pierwsze 9 do second, a ty zwracasz 9.
Aktualizowanie second tylko wtedy, gdy pojawia się nowe maksimum. W przypadku [10, 20, 15] wartość 15 nigdy nie trafia do second, a ty zwracasz 10.
Usuwanie duplikatów za pomocą zbioru, a następnie sortowanie. To działa, ale wymaga O(n) pamięci i O(n log n) czasu, choć wystarczy jedno przejście.

Najczęstsze pytania4

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.

Co należy zwrócić, gdy nie ma drugiej największej wartości?

Tutaj nie może się to zdarzyć: lista zawsze zawiera dwie różne wartości. Ogólnie lista taka jak [4, 4, 4] nie ma rozwiązania, więc zwrócisz znacznik, taki jak -1 lub null, albo zgłosisz błąd. Możesz wykryć ten przypadek, gdy po pętli second nadal przechowuje swoją początkową wartość.

Python

def secondLargest(nums):
    # Napisz tutaj kod

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

nums = [4, 9, 2, 7, 9]

Oczekiwane

Second Largest Number

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Sortuj i zejdź w dół poniżej maksimum

Dwa przebiegi

Jedno przejście śledzące dwa największe

Pułapki i przypadki brzegowe

Najczęstsze pytania4

Podobne zadania