Majority Element

+10

Ti viene dato un array di numeri interi nums di lunghezza n. Un valore compare al suo interno più di n / 2 volte e quel valore è chiamato elemento maggioritario. Restituiscilo. Un valore che occupa più della metà dell’array è sempre unico, quindi esiste esattamente una risposta.

Funzione

majorityElement(nums: integer-array) → integer

numsinteger-array: l'array di numeri interi, con un valore che ne occupa più della metà
Restituisceinteger: il valore che compare più di n / 2 volte

Vincoli

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Un valore compare più di nums.length / 2 volte.

Esempi

Input: nums = [3, 9, 3, 3, 4]
Output: 3
Spiegazione: 3 compare tre volte in cinque elementi. Tre è maggiore di 5 / 2 = 2.5, e 9 e 4 compaiono una volta ciascuno.

+15 test nascosti all’invio

Per approfondire

Riesci a trovare l’elemento maggioritario in tempo O(n) con O(1) memoria aggiuntiva, senza ordinare l’array?

Soluzione

Contare quante volte compare ogni valore risponde alla domanda, ma per i conteggi serve una mappa hash. Per farne a meno, basta vedere cosa rende speciale il valore maggioritario: è più numeroso di tutti gli altri valori messi insieme. Abbina ogni sua copia a un valore diverso e cancella entrambi: ne rimarranno sempre alcune copie. Il voto di Boyer-Moore realizza questi abbinamenti in un solo passaggio, con un candidato e un contatore.

Conta con una mappa hash

Intuizione

Scorri l'array e mantieni una mappa hash che associ a ogni valore il numero di volte che lo hai visto. Dopo aver incrementato di uno il conteggio di un valore, controlla se ora è maggiore della metà della lunghezza. Il primo valore a superare quella soglia è la maggioranza, quindi puoi restituirlo subito.

Per [3, 9, 3, 3, 4], il conteggio di 3 diventa 1 all'indice 0, 2 all'indice 2 e 3 all'indice 3. Tre occorrenze su cinque sono più di 2.5, quindi restituisci 3 senza leggere l'ultimo elemento.

La ricerca e l'aggiornamento in una mappa hash richiedono O(1) in media, quindi il tempo è O(n). La mappa può contenere fino a circa n / 2 valori diversi, quindi la memoria aggiuntiva è O(n). Il prossimo approccio elimina la mappa.

Algoritmo

Crea una mappa vuota da valore a conteggio.
Per ogni elemento x, aggiungi 1 al conteggio di x.
Se quel conteggio moltiplicato per 2 è maggiore della lunghezza dell'array, restituisci x.

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

Voto di Boyer-Moore

Intuizione

Considera l’array come un’elezione. Tieni un candidate e un count dei suoi voti che non sono ancora stati annullati. Un elemento uguale al candidato aggiunge un voto. Un elemento diverso annulla un voto, e i due abbandonano insieme la corsa. Quando il conteggio è 0, l’elemento successivo diventa il nuovo candidato.

Perché il valore rimasto alla fine è quello di maggioranza: ogni annullamento rimuove due valori diversi, quindi rimuove al massimo una copia del valore di maggioranza. Supponiamo che il valore di maggioranza compaia m volte. Ci sono solo n - m altri elementi, meno di m, quindi non possono annullare tutte le copie. Tutti i voti ancora presenti alla fine appartengono al candidato finale, e tra questi c’è una copia del valore di maggioranza, quindi il candidato è il valore di maggioranza.

In [8, 8, 1, 1, 8, 1, 8] il conteggio passa per 1, 2, 1, 0: i due 1 hanno annullato entrambi gli 8. L’8 successivo ricomincia con un conteggio di 1, l’1 successivo lo annulla e l’ultimo 8 ridiventa il candidato. Restituisci 8. Una passata con due variabili richiede tempo O(n) e memoria O(1).

Algoritmo

Imposta candidate sul primo elemento e count a 0.
Per ogni elemento x, se count è 0, imposta x come candidato.
Se x è uguale al candidato, aggiungi 1 a count. Altrimenti sottrai 1.
Dopo l'ultimo elemento, restituisci 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

Trappole e casi limite

La maggior parte delle risposte errate deriva dalla soglia della metà o dal dare troppo peso al contatore.

«Più della metà» è una condizione stretta. count >= n / 2 accetta 2 occorrenze su 4, che non costituiscono una maggioranza. Confronta count * 2 > n e nessun arrotondamento potrà interferire.
Il valore finale di count in Boyer-Moore non indica quante volte compare l’elemento maggioritario. Per [8, 8, 1, 1, 8, 1, 8] termina a 1, mentre 8 compare quattro volte.
Inizializzare candidate = nums[0] e count = 1 funziona solo se poi il ciclo inizia dall’indice 1. Se lo fai iniziare dall’indice 0, il primo elemento vota due volte: con [1, 2, 2] il contatore termina a 0 e restituisci 1.
Boyer-Moore si basa sulla garanzia. Su [1, 2, 3], che non ha una maggioranza, restituisce comunque 3. Se un input potrebbe non avere una maggioranza, conta il candidato una seconda volta prima di fidarti del risultato.

Domande frequenti4

Che cos'è l'algoritmo di voto di Boyer-Moore?

Trova il valore che compare in più della metà degli elementi di una lista in un solo passaggio con memoria O(1). Mantiene un candidato e un contatore: un elemento corrispondente aggiunge uno, un elemento diverso sottrae uno e, quando il contatore è 0, l’elemento successivo diventa il candidato. Poiché il valore maggioritario supera la somma di tutti gli altri valori, è il candidato che rimane alla fine.

Qual è la complessità temporale e spaziale di Majority Element?

Il voto di Boyer-Moore richiede un tempo O(n) e uno spazio aggiuntivo O(1). Anche il conteggio con una hash map richiede un tempo O(n), ma necessita di uno spazio O(n) per i conteggi. Ordinare prima richiede un tempo O(n log n).

È possibile risolvere il problema dell’elemento maggioritario ordinando?

Sì. Dopo l'ordinamento, tutte le copie dell'elemento maggioritario si trovano in un unico blocco più lungo della metà dell'array, e un blocco del genere copre la posizione centrale. Quindi l'elemento all'indice n / 2, arrotondato per difetto, è la risposta. È breve da scrivere, ma richiede un tempo O(n log n).

Che cosa succede se l’array potrebbe non avere un elemento maggioritario?

Boyer-Moore restituisce sempre un candidato, anche quando nessun valore occupa più della metà dell’array. Aggiungi un secondo passaggio che conta il candidato e accettalo solo se il conteggio è maggiore di n / 2. Il totale rimane O(n) come tempo e O(1) come spazio.

Python

def majorityElement(nums):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Input

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

Atteso