Majority Element

+10

Otrzymujesz tablicę liczb całkowitych nums o długości n. Jedna wartość występuje w niej więcej niż n / 2 razy i nazywa się elementem większościowym. Zwróć ją. Wartość, która występuje w więcej niż połowie elementów tablicy, jest zawsze unikalna, więc istnieje dokładnie jedna odpowiedź.

Funkcja

majorityElement(nums: integer-array) → integer

numsinteger-array: tablica liczb całkowitych, w której jedna wartość zajmuje więcej niż połowę
Zwracainteger: wartość, która pojawia się więcej niż n / 2 razy

Ograniczenia

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Jedna wartość występuje więcej niż nums.length / 2 razy.

Przykłady

Wejście: nums = [3, 9, 3, 3, 4]
Wyjście: 3
Wyjaśnienie: 3 występuje trzy razy wśród pięciu elementów. Trzy to więcej niż 5 / 2 = 2.5, a 9 i 4 występują po jednym razie.

+15 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy potrafisz znaleźć element większościowy w czasie O(n), używając O(1) dodatkowej pamięci, bez sortowania tablicy?

Rozwiązanie

Policzenie, jak często pojawia się każda wartość, odpowiada na pytanie, ale do zliczenia potrzebna jest mapa mieszająca. Można z niej zrezygnować, zauważając, co wyróżnia większość: występuje częściej niż wszystkie pozostałe wartości razem wzięte. Połącz każdą jej kopię z inną wartością i skreśl obie — wtedy zawsze pozostanie kilka jej kopii. Algorytm głosowania Boyera-Moore’a wykonuje takie parowanie w jednym przebiegu, używając jednego kandydata i jednego licznika.

Zliczanie za pomocą mapy haszującej

Intuicja

Przejdź przez tablicę i przechowuj mapę haszującą, która przypisuje każdej wartości liczbę jej wystąpień. Po zwiększeniu licznika danej wartości o jeden sprawdź, czy jest teraz większy niż połowa długości tablicy. Pierwsza wartość, która przekroczy ten próg, jest większością, więc możesz od razu ją zwrócić.

Dla [3, 9, 3, 3, 4] licznik wartości 3 wynosi 1 na indeksie 0, 2 na indeksie 2 i 3 na indeksie 3. Trzy wystąpienia na pięć to więcej niż 2.5, więc zwracasz 3, nie odczytując ostatniego elementu.

Wyszukiwanie w mapie haszującej i aktualizacja zajmują średnio O(1), więc czas działania wynosi O(n). Mapa może przechowywać do około n / 2 różnych wartości, więc dodatkowe zużycie pamięci wynosi O(n). Kolejne podejście pozwala pozbyć się mapy.

Algorytm

Utwórz pustą mapę przypisującą wartość do liczby wystąpień.
Dla każdego elementu x zwiększ liczbę wystąpień x o 1.
Jeśli ta liczba wystąpień pomnożona przez 2 jest większa niż długość tablicy, zwróć x.

def majorityElement(nums):
    counts = {}
    for x in nums:
        counts[x] = counts.get(x, 0) + 1
        if counts[x] * 2 > len(nums):
            return x

Głosowanie Boyera-Moore’a

Intuicja

Potraktuj tablicę jak wybory. Zachowaj jednego candidate i count jego głosów, których nic jeszcze nie anulowało. Element równy kandydatowi dodaje głos. Element, który się od niego różni, anuluje jeden głos, a oba elementy wspólnie wycofują się z wyścigu. Gdy licznik wynosi 0, następny element staje się nowym kandydatem.

Dlaczego wartość pozostała na końcu jest większościowa: każde anulowanie usuwa dwie różne wartości, więc usuwa najwyżej jedną kopię wartości większościowej. Załóżmy, że wartość większościowa występuje m razy. Pozostałych elementów jest tylko n - m, czyli mniej niż m, więc nie mogą anulować wszystkich jej kopii. Każdy głos, który pozostaje na końcu, należy do ostatecznego kandydata, a wśród nich jest kopia wartości większościowej, więc kandydat jest wartością większościową.

Dla [8, 8, 1, 1, 8, 1, 8] licznik przyjmuje kolejno wartości 1, 2, 1, 0: dwie jedynki anulowały obie ósemki. Następna ósemka zaczyna od nowa z licznikiem równym 1, kolejna jedynka ją anuluje, a ostatnia ósemka znów zostaje kandydatem. Zwracasz 8. Jedno przejście i dwie zmienne dają czas O(n) i pamięć O(1).

Algorytm

Ustaw candidate na pierwszy element, a count na 0.
Dla każdego elementu x, jeśli count wynosi 0, ustaw x jako kandydata.
Jeśli x jest równy kandydatowi, dodaj 1 do count. W przeciwnym razie odejmij 1.
Po ostatnim elemencie zwróć candidate.

def majorityElement(nums):
    candidate = nums[0]
    count = 0
    for x in nums:
        if count == 0:
            candidate = x  # the old candidate's votes are used up
        if x == candidate:
            count += 1
        else:
            count -= 1  # x and one copy of the candidate cancel out
    return candidate

Pułapki i przypadki brzegowe

Większość błędnych odpowiedzi wynika z pomylenia warunku większości albo z nadinterpretowania licznika.

„Więcej niż połowa” oznacza warunek ścisły. count >= n / 2 akceptuje 2 wystąpienia na 4, co nie stanowi większości. Porównaj count * 2 > n — wtedy zaokrąglanie nie może wpłynąć na wynik.
Końcowa wartość count w algorytmie Boyera–Moore’a nie określa, ile razy występuje większość. Dla [8, 8, 1, 1, 8, 1, 8] wynosi 1, podczas gdy 8 występuje cztery razy.
Rozpoczęcie od candidate = nums[0] i count = 1 działa tylko wtedy, gdy pętla rozpoczyna się od indeksu 1. Jeśli zaczniesz ją od indeksu 0, pierwszy element zagłosuje dwa razy: dla [1, 2, 2] licznik kończy na 0 i zwracasz 1.
Algorytm Boyera–Moore’a opiera się na gwarancji istnienia większości. Dla [1, 2, 3], w którym nie ma większości, i tak zwraca 3. Jeśli dane wejściowe mogą nie zawierać większości, zlicz wystąpienia kandydata w drugim przebiegu, zanim mu zaufasz.

Najczęstsze pytania4

Czym jest algorytm głosowania Boyera-Moore’a?

Znajduje wartość, która występuje w ponad połowie elementów listy, w jednym przebiegu i przy użyciu pamięci O(1). Przechowuje kandydata i licznik: pasujący element zwiększa licznik o jeden, inny element zmniejsza go o jeden, a gdy osiągnie 0, następny element zostaje kandydatem. Ponieważ większość występuje częściej niż wszystkie pozostałe wartości łącznie, na końcu zostaje ona kandydatem.

Jaka jest złożoność czasowa i pamięciowa problemu elementu większościowego?

Głosowanie Boyera-Moore’a działa w czasie O(n) i wymaga dodatkowej pamięci O(1). Zliczanie za pomocą mapy haszującej również działa w czasie O(n), ale wymaga O(n) pamięci na zliczenia. Wcześniejsze sortowanie zajmuje czas O(n log n).

Czy problem elementu większościowego można rozwiązać przez sortowanie?

Tak. Po posortowaniu wszystkie kopie elementu większościowego znajdują się w jednym bloku dłuższym niż połowa tablicy, a każdy taki blok obejmuje środkową pozycję. Zatem element o indeksie n / 2, zaokrąglonym w dół, jest odpowiedzią. To krótki zapis, ale wymaga czasu O(n log n).

Co, jeśli tablica może nie zawierać elementu większościowego?

Boyer-Moore zawsze zwraca jakiegoś kandydata, nawet gdy żadna wartość nie występuje w więcej niż połowie tablicy. Dodaj drugie przejście, które zlicza wystąpienia kandydata, i zaakceptuj go tylko wtedy, gdy ich liczba jest większa niż n / 2. Łączna złożoność pozostaje równa O(n) czasowo i O(1) pod względem pamięci.

Python

def majorityElement(nums):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Wejście

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

Oczekiwane