Find the Largest Number

Q: Jaka jest złożoność czasowa znajdowania maksimum w tablicy?

Jedno przejście zajmuje O(n) czasu i O(1) dodatkowej przestrzeni. Żadna metoda działająca na nieposortowanej tablicy nie może być szybsza, ponieważ każdy element, którego nie odczytasz, może być największy. Wcześniejsze sortowanie kosztuje O(n log n) , co jest wolniejsze i nic nie daje.

PoczątkującyTablice i napisy

+10

Otrzymujesz niepustą listę liczb całkowitych nums. Zwróć największą wartość z tej listy. Wartości mogą być ujemne, więc odpowiedź również może być ujemna. Znajdź ją, wykonując własne porównania, bez użycia wbudowanej funkcji maksimum, takiej jak max.

Funkcja

findMax(nums: integer-array) → integer

numsinteger-array: lista liczb całkowitych do wyszukania
Zwracainteger: największa wartość w nums

Ograniczenia

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹

Przykłady

Wejście: nums = [3, 17, 4, 12, 9]
Wyjście: 17
Wyjaśnienie: Czytając od lewej, największą dotychczasową wartością jest 3, a następnie 17. Żadna z wartości 4, 12 ani 9 nie jest większa niż 17, więc odpowiedzią jest 17.

Wejście: nums = [-8, -3, -11, -3]
Wyjście: -3
Wyjaśnienie: Każda wartość jest ujemna, a -3 jest najbliżej zera, więc jest największa. Pojawia się dwa razy, ale zwracasz wartość, a nie jej pozycję.

+13 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy możesz zwrócić zarówno największą, jak i najmniejszą wartość, wykonując około 3n/2 porównań zamiast 2n, najpierw porównując wartości parami?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Każda pominięta wartość może być największa, więc każde rozwiązanie odczytuje każdy element co najmniej raz. Jedyną rzeczywistą decyzją jest to, od czego zaczyna się bieżące maksimum. Zacznij od pierwszego elementu, nigdy od 0, ponieważ każda wartość na liście może być ujemna.

Posortuj kopię i pobierz ostatnią wartość

Intuicja

Na liście posortowanej od najmniejszej do największej wartości największa wartość znajduje się na końcu. Skopiuj nums, aby lista wywołującego pozostała bez zmian, posortuj kopię i zwróć jej ostatni element. Dla [3, 17, 4, 12, 9] posortowana kopia to [3, 4, 9, 12, 17], a ostatni element to 17.

Odpowiedź jest poprawna, ale sortowanie robi znacznie więcej, niż potrzebujesz. Ustawia wszystkie wartości w kolejności, co wymaga około n log n porównań, czyli mniej więcej 60,000 dla n = 5000, gdy chcesz znaleźć tylko największą wartość. Kopia zużywa też O(n) pamięci.

W JavaScript i TypeScript przekaż komparator do sort. Bez niego porównuje liczby jako tekst, przez co 12 i 17 trafiają przed 3.

Algorytm

Skopiuj nums.
Posortuj kopię od najmniejszej do największej wartości, porównując liczby jako liczby.
Zwróć ostatni element posortowanej kopii.

def findMax(nums):
    ordered = sorted(nums)  # a sorted copy, smallest first
    return ordered[-1]

Jedno przejście z bieżącym maksimum

Intuicja

Przechowuj największą dotąd napotkaną wartość w jednej zmiennej, largest. Ustaw ją na nums[0], porównuj z każdą wartością i zastępuj ją, gdy napotkasz większą wartość. Gdy pętla się zakończy, largest będzie porównana z każdym elementem, więc żaden element listy nie będzie od niej większy.

Dla [3, 17, 4, 12, 9] zmienna largest zaczyna od 3, zmienia się na 17 i pozostaje równa 17 dla 4, 12 i 9. To n-1 przydatnych porównań i jedna dodatkowa zmienna.

To właśnie rozpoczęcie od nums[0] sprawia, że metoda działa dla list zawierających liczby ujemne. Jeśli zamiast tego zaczniesz od 0, żadna wartość z [-8, -3, -11, -3] nie będzie większa, więc zwrócisz 0 — wartość, której nawet nie ma na liście.

Algorytm

Ustaw largest na nums[0].
Przejdź pętlą po każdej wartości x w nums.
Jeśli x > largest, ustaw largest na x.
Po zakończeniu pętli zwróć largest.

def findMax(nums):
    largest = nums[0]  # never 0: every value may be negative
    for x in nums:
        if x > largest:
            largest = x
    return largest

Pułapki i przypadki brzegowe

Pętla jest krótka, więc błędy dotyczą tego, gdzie się zaczyna i co odczytuje.

Ustawienie largest na początku na 0 lub -1. Każda lista, której wartości są mniejsze od tej początkowej, zwróci liczbę, której nie ma na liście.
Ustawienie na początku wymyślonej małej liczby, takiej jak -1000000. Wartości w tym przypadku sięgają -10^9, więc wartość początkowa i tak będzie większa. nums[0] nie wymaga zgadywania.
Odczytywanie nums[0] w Lua lub R, gdzie pierwszy element to nums[1]. Lua zwraca nil, a R zwraca pusty wektor.
Użycie w pętli warunku i ≤ n w języku z indeksami zaczynającymi się od 0, co powoduje odczyt jednego elementu poza końcem.
Sortowanie bez komparatora numerycznego w JavaScript lub TypeScript. Porządek tekstowy elementów [3, 17, 4, 12, 9] kończy się na 9, więc zwracasz 9 zamiast 17.

Najczęstsze pytania4

Jaka jest złożoność czasowa znajdowania maksimum w tablicy?

Jedno przejście zajmuje O(n) czasu i O(1) dodatkowej przestrzeni. Żadna metoda działająca na nieposortowanej tablicy nie może być szybsza, ponieważ każdy element, którego nie odczytasz, może być największy. Wcześniejsze sortowanie kosztuje O(n log n), co jest wolniejsze i nic nie daje.

Jak znaleźć największą liczbę w tablicy bez użycia funkcji max?

Zapisz pierwszy element w zmiennej. Przejdź pętlą po pozostałych elementach i za każdym razem, gdy element jest większy niż wartość zmiennej, zapisz w niej ten element. Po zakończeniu pętli zmienna zawiera największą wartość.

Dlaczego maksimum bieżące powinno zaczynać się od pierwszego elementu, a nie od 0?

Jeśli każda wartość jest ujemna, żadna z nich nie jest większa od 0, więc maksimum, które zaczyna się od 0, nigdy się nie zmienia, a funkcja zwraca 0. Pierwszy element zawsze jest rzeczywistym kandydatem, więc rozpoczęcie od niego jest poprawne dla każdej listy. Najmniejsza liczba całkowita w danym języku również się sprawdzi, o ile lista nigdy nie jest pusta.

Kiedy sortowanie jest dobrym sposobem na znalezienie największej wartości?

Gdy potrzebujesz czegoś więcej niż największej wartości, na przykład trzech największych wartości lub mediany, i zamierzasz zadawać wiele takich pytań o tę samą listę. W przypadku pojedynczego maksimum jedno przejście jest szybsze i nie zmienia listy.

Python

def findMax(nums):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

nums = [3, 17, 4, 12, 9]

Oczekiwane