Leaders in an Array

+10

Otrzymujesz tablicę liczb całkowitych nums. Element jest liderem, jeśli jest większy lub równy każdemu elementowi po jego prawej stronie. Ostatni element nie ma żadnych elementów po prawej stronie, więc zawsze jest liderem. Zwróć wszystkich liderów w kolejności, w jakiej występują w nums, od lewej do prawej.

Funkcja

leaders(nums: integer-array) → integer-array

numsinteger-array: tablica liczb całkowitych do przeszukania
Zwracainteger-array: liderzy nums, od lewej do prawej

Ograniczenia

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

Przykłady

Wejście: nums = [12, 5, 9, 3, 6, 2]
Wyjście: [12, 9, 6, 2]
Wyjaśnienie: 2 jest ostatnia, więc prowadzi. 6 pokonuje poprzedzającą ją 2, 9 pokonuje 3, 6 i 2, a 12 pokonuje wszystkie pozostałe. 5 przegrywa z 9, a 3 przegrywa z 6, więc odpowiedź to [12, 9, 6, 2].

Pytanie dodatkowe

Jeśli wartości napływają pojedynczo i po każdej z nich musisz wskazać dotychczasowych liderów, jak aktualizować listę w zamortyzowanym czasie O(1) na każdą wartość?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Czytając od lewej, każdy element wymaga ponownego sprawdzenia swojego sufiksu. Zamiast tego przejdź od prawej: jedyne, co musisz wiedzieć o sufiksie, to jego największa wartość, a wystarczy przechowywać ją w jednej zmiennej. Dzięki temu sprawdzanie w czasie O(n²) zamienia się w pojedyncze przejście.

Sprawdź wszystko po prawej stronie

Poprawne, ale nie kończy się na największych testach

Intuicja

Zastosuj definicję: dla każdego indeksu i przeglądaj kolejne elementy i zatrzymaj się na pierwszym, który jest ściśle większy od nums[i]. Jeśli przeglądanie dotrze do końca, nums[i] jest liderem. Sprawdzasz indeksy od lewej do prawej, więc liderzy pojawiają się w tej kolejności. W [12, 5, 9, 3, 6, 2] liczba 5 zatrzymuje się na 9, a liczba 3 na 6.

Koszt wynika z przeglądania, które dochodzi do końca. Przy 24,999 jednakowych wartościach, po których następuje jedna większa wartość, każdy element przegląda niemal całą tablicę: około 25,000 × 25,000 / 2, czyli ponad 3 × 10^8 porównań.

Algorytm

Utwórz pustą listę wynikową.
Dla każdego indeksu i sprawdzaj kolejne wartości j od i + 1 do końca.
Jeśli któreś nums[j] jest większe niż nums[i], przerwij: nums[i] nie jest liderem.
Jeśli nie istnieje takie j, dodaj nums[i] do wyniku.
Zwróć wynik.

def leaders(nums):
    n = len(nums)
    result = []
    for i in range(n):
        is_leader = True
        for j in range(i + 1, n):
            if nums[j] > nums[i]:  # a bigger value on the right rules it out
                is_leader = False
                break
        if is_leader:
            result.append(nums[i])
    return result

Jedno przejście od prawej strony z bieżącym maksimum

Intuicja

Bycie co najmniej tak dużym jak każdy element po prawej stronie jest tym samym co bycie co najmniej tak dużym jak ich maksimum. Idąc od prawej do lewej, możesz na bieżąco aktualizować to maksimum. Ostatni element jest liderem i wyznacza maksimum. Każdy element po jego lewej stronie jest liderem, gdy jest co najmniej tak duży jak maksimum, a następnie staje się nowym maksimum; w przeciwnym razie po jego prawej stronie znajduje się większa wartość.

Dla [12, 5, 9, 3, 6, 2]: liderem jest 2, potem 6, potem 9, a następnie 12, natomiast 3 i 5 są mniejsze od maksimum. Otrzymujesz [2, 6, 9, 12]; po odwróceniu to jest odpowiedź.

Każdy element jest porównywany raz: czas O(n) i O(1) dodatkowej pamięci poza wynikiem. Wersja w R oznacza liderów w wektorze logical(n), więc jej dodatkowa pamięć wynosi O(n).

Algorytm

Umieść ostatni element w wyniku i ustaw best na jego wartość.
Przesuwaj i od przedostatniego indeksu w dół do 0.
Jeśli nums[i] ≥ best, dodaj nums[i] do wyniku i ustaw best na jego wartość.
Odwróć wynik, aby elementy dominujące były ułożone od lewej do prawej, i zwróć go.

def leaders(nums):
    n = len(nums)
    best = nums[n - 1]  # the largest value to the right of the current index
    found = [best]      # the last element is always a leader
    for i in range(n - 2, -1, -1):
        if nums[i] >= best:
            best = nums[i]
            found.append(nums[i])
    found.reverse()  # collected right to left, returned left to right
    return found

Pułapki i przypadki brzegowe

Używanie > zamiast ≥ przy porównywaniu z dotychczasowym maksimum. W [4, 7, 7, 1, 7] każde 7 jest liderem, ale ścisłe porównanie zachowuje tylko ostatnie.
Ustawianie maksimum na 0 zamiast na ostatnim elemencie. [-1, -5] musi zwrócić oba elementy, ale maksimum równe 0 je wyklucza.
Zwracanie liderów w kolejności, w jakiej zostały znalezione: [2, 6, 9, 12] zamiast [12, 9, 6, 2].
Dodanie ostatniego elementu dwa razy przez rozpoczęcie pętli od ostatniego indeksu po wcześniejszym dodaniu go do wyniku.
Porównywanie każdego elementu tylko z jego sąsiadem. W [5, 3, 9] 5 jest większe od sąsiadującej z nim 3, ale 9 sprawia, że odpowiedzią jest [9].

Najczęstsze pytania3

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

O(n) przy jednym przejściu od prawej strony, ponieważ każdy element jest porównywany z bieżącą wartością maksymalną tylko raz. Sprawdzanie każdego elementu w porównaniu ze wszystkimi elementami po jego prawej stronie wymaga w najgorszym przypadku O(n²), na przykład gdy wszystkie wartości są równe.

Czy ostatni element zawsze jest liderem?

Tak. Element wiodący musi być co najmniej tak duży jak każdy element po jego prawej stronie, a ostatni element nie ma żadnych elementów po prawej, więc warunek jest spełniony i nie trzeba niczego sprawdzać.

Czy równe wartości liczą się jako liderzy?

Tutaj tak: lider musi być większy lub równy każdemu elementowi po swojej prawej stronie, więc w [4, 7, 7, 1, 7] wszystkie trzy siódemki są liderami. W niektórych wersjach wymaga się, by był ściśle większy; wtedy porównuj za pomocą > i liderem jest tylko ostatnia z równych wartości.

def leaders(nums):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argument

nums = [12, 5, 9, 3, 6, 2]

Oczekiwany wynik

[12, 9, 6, 2]