Trova l’elemento di maggioranza nell’array

L’elemento di maggioranza è l’elemento che si verifica più della metà della dimensione dell’array.

Come trovare l’elemento di maggioranza in un array in O(n) ?

Esempio di input:

 {2,1,2,3,4,2,1,2,2} 

Uscita prevista:

 2 

L’elemento di maggioranza (se esiste) sarà anche la mediana. Possiamo trovare la mediana in O (n) e quindi verificare che sia effettivamente un elemento di maggioranza valido in O (n). Maggiori dettagli per il link di implementazione

 // returns -1 if there is no element that is the majority element, otherwise that element // funda :: if there is a majority element in an array, say x, then it is okay to discard // a part of that array that has no majority element, the remaining array will still have // x as the majority element // worst case complexity : O(n) int findMajorityElement(int* arr, int size) { int count = 0, i, majorityElement; for (i = 0; i < size; i++) { if (count == 0) majorityElement = arr[i]; if (arr[i] == majorityElement) count++; else count--; } count = 0; for (i = 0; i < size; i++) if (arr[i] == majorityElement) count++; if (count > size/2) return majorityElement; return -1; } 

È triste vedere che in 5 anni nessuno ha scritto una spiegazione adeguata per questo problema.

Questo è un problema standard negli algoritmi di streaming (dove hai un enorme stream di dati potenzialmente infinito) e devi calcolare alcune statistiche da questo stream, passando attraverso questo stream una volta.


Chiaramente puoi avvicinarti con l’hashing o l’ordinamento, ma con un stream potenzialmente infinito puoi chiaramente esaurire la memoria. Quindi devi fare qualcosa di intelligente qui.


L’elemento di maggioranza è l’elemento che si verifica più della metà della dimensione dell’array . Ciò significa che l’elemento di maggioranza si verifica più di tutti gli altri elementi combinati. Cioè, se si conta il numero di volte che l’elemento di maggioranza appare e si sottrae il numero di occorrenze di tutti gli altri elementi, si otterrà un numero positivo.

Quindi se conti le occorrenze di qualche elemento e sottrai il numero di occorrenze di tutti gli altri elementi e ottieni il numero 0, allora il tuo elemento originale non può essere un elemento di maggioranza. Questa è la base per un algoritmo corretto:

Dichiarare due variabili, counter e possible_element. Iterate il stream, se il contatore è 0 – sovrascrivete l’elemento ansible e inizializzate il contatore, se il numero è uguale all’elemento ansible – aumentare il contatore, altrimenti diminuirlo. Codice Python:

 def majority_element(arr): counter, possible_element = 0, None for i in arr: if counter == 0: possible_element, counter = i, 1 elif i == possible_element: counter += 1 else: counter -= 1 return possible_element 

È chiaro che l’algoritmo è O(n) con una costante molto piccola prima di O(n) (come 3). Inoltre sembra che la complessità dello spazio sia O(1) , perché abbiamo solo tre variabili inizializzate. Il problema è che una di queste variabili è un contatore che potenzialmente può crescere fino a n (quando l’array consiste degli stessi numeri). E per memorizzare il numero n è necessario lo spazio O(log (n)) . Quindi dal punto di vista teorico è O(n) tempo e O(log(n)) spazio. Dal pratico , puoi inserire un numero 2 ^ 128 in un longint e questo numero di elementi nell’array è inimmaginabilmente enorme.

Si noti inoltre che l’algoritmo funziona solo se esiste un elemento di maggioranza. Se tale elemento non esiste, restituirà comunque un numero, che sarà sicuramente sbagliato. (è facile modificare l’algoritmo per stabilire se esiste l’elemento di maggioranza)

Canale storico: questo algoritmo è stato inventato da qualche parte nel 1982 da Boyer, Moore e chiamato l’ algoritmo di voto a maggioranza Boyer-Moore

Elemento di maggioranza:

Un elemento di maggioranza in una matrice A [] di dimensione n è un elemento che appare più di n / 2 volte (e quindi c’è al massimo un tale elemento).

Trovare un candidato:

L’algoritmo per la prima fase che funziona in O (n) è noto come Algoritmo di voto di Moore. L’idea di base dell’algoritmo è se cancelliamo ogni occorrenza di un elemento e con tutti gli altri elementi che sono diversi da e allora e esisterà fino alla fine se è un elemento di maggioranza.

 findCandidate(a[], size) 1. Initialize index and count of majority element maj_index = 0, count = 1 2. Loop for i = 1 to size – 1 (a)If a[maj_index] == a[i] count++ (b)Else count--; (c)If count == 0 maj_index = i; count = 1 3. Return a[maj_index] 

Al di sopra dell’algoritmo scorre ogni elemento e mantiene il conteggio di un [maj_index], Se l’elemento successivo è lo stesso, incrementa il conteggio, se l’elemento successivo non è lo stesso diminuisce il conteggio e se il conteggio raggiunge 0 allora cambia maj_index all’attuale l’elemento e gli insiemi contano fino a 1. L’algoritmo First Phase ci fornisce un elemento candidato. Nella seconda fase dobbiamo verificare se il candidato è davvero un elemento di maggioranza.

La seconda fase è semplice e può essere facilmente eseguita in O (n). Abbiamo solo bisogno di verificare se il conteggio dell’elemento candidato è maggiore di n / 2.

Leggi geeksforgeeks per maggiori dettagli

Tempo: O (n)

Spazio: O (n)

Cammina sull’albero e conta l’occorrenza degli elementi in una tabella hash.

Ora: O (n lg n) o O (n * m) (dipende dall’ordinamento utilizzato)

Spazio: (1)

ordina l’array quindi conta le occorrenze degli elementi.

La risposta corretta all’intervista: Algoritmo di voto di Moore

Ora: O (n)

Spazio: O (1)

Cammina sulla lista confronta il numero corrente con il numero di ipotesi migliore attuale. Se il numero è uguale al numero corrente migliore, aumenta un contatore, altrimenti decrementa il contatore e se il contatore raggiunge zero sostituisci il numero corrente migliore con il numero corrente e imposta il contatore su 1. Quando arrivi alla fine la migliore ipotesi è il numero di Candidato, ripercorri la lista solo contando le istanze del candidato. Se il conteggio finale è maggiore di n / 2, allora è il numero di maggioranza altrimenti non ce n’è uno.

Che ne dici di un approccio di campionamento casuale? È ansible campionare, ad esempio, gli elementi sqrt (n) e per ogni elemento che si è verificato più di sqrt (n) / 4 volte (può essere eseguito in modo ingenuo nel tempo O (n) e nello spazio O (sqrt (n)), è ansible controllare se fosse un elemento di maggioranza nel tempo O (n).

Questo metodo trova la maggioranza con alta probabilità perché l’elemento di maggioranza dovrebbe essere campionato almeno sqrt (n) / 2 volte in aspettativa, con una deviazione standard di al massimo n ^ {1/4} / 2.

Un altro approccio di campionamento simile a un approccio che ho visto in uno dei collegamenti duplicati consiste nel disegnare due campioni e, se sono uguali, verificare di aver trovato l’elemento di maggioranza nel tempo O (n). La fase di verifica aggiuntiva è necessaria perché gli altri elementi oltre alla maggioranza potrebbero non essere distinti.

Nell’algoritmo di Monte-Carlo,

 Majority (a,n) //a[]-array of 'n' natural numbers { j=random(0,1,....,n-1) /*Selecting the integers at random ranging from 0 to n-1*/ b=a[j];c=0; for k from 0 to n-1 do { if a[k]=b then, c=c+1; } return (c>n/2) } 

Per trovare la maggior parte di un elemento in un array, è ansible utilizzare l’algoritmo di voto di maggioranza di Moore, che è uno dei migliori algoritmi per esso.

Complessità del tempo: O(n) or linear time

Complessità spaziale: O(1) or constant space

Maggiori informazioni su Major Algorithm e GeeksforGeeks di Moore

Se si è autorizzati a creare una tabella hash e si assume che la ricerca di voci hash sia costante, basta hash_map ogni voce rispetto al numero di occorrenze.

Potresti fare un secondo passaggio attraverso il tavolo che ottieni quello con il conteggio più alto, ma se conosci in anticipo il numero di elementi nella tabella, saprai immediatamente se abbiamo un elemento di maggioranza sul primo passaggio quando colpiamo il richiesto contare sull’elemento.

Naturalmente non è ansible garantire che vi sia anche una sequenza di 2 occorrenze consecutive dell’elemento, ad esempio 1010101010101010101 non ha 1s consecutivi ma è un elemento di maggioranza.

Non ci viene detto nulla sul fatto che ci sia qualche tipo di ordinamento sul tipo di elemento anche se ovviamente dobbiamo essere in grado di confrontare due per l’uguaglianza.

  int majorityElement(int[] num) { int major=num[0], count = 1; for(int i=1; i 

Complessità temporale O (n)

 public class MajorityElement { public static void main(String[] args) { int arr[]={3,4,3,5,3,90,3,3}; for(int i=0;i=arr.length/2) { System.out.println("majority element"+arr[i]); break; } } } 

}

Una versione modificata dell’algoritmo di Boyer,

  • 3 passaggi dove,
    • Nel primo passaggio, eseguiamo un’iterazione diretta dell’array
    • Nel secondo passaggio, eseguiamo un’iterazione inversa dell’array.
    • Nel terzo passaggio, ottiene il conteggio per entrambi gli elementi maggioritari ottenuti in primo e secondo passaggio.

Tecnicamente un algoritmo di complessità lineare (O (3n)). Credo che questo dovrebbe funzionare per un array con un elemento di maggioranza che si verifica almeno n / 2 volte.

 #include  #include  template  DataType FindMajorityElement(std::vector arr) { // Modified BOYERS ALGORITHM with forward and reverse passes // Count will stay positive if there is a majority element auto GetMajority = [](auto seq_begin, auto seq_end) -> DataType{ int count = 1; DataType majority = *(seq_begin); for (auto itr = seq_begin+1; itr != seq_end; ++itr) { count += (*itr == majority) ? 1 : -1; if (count <= 0) { // Flip the majority and set the count to zero whenever it falls below zero majority = *(itr); count = 0; } } return majority; }; DataType majority1 = GetMajority(arr.begin(), arr.end()); DataType majority2 = GetMajority(arr.rbegin(), arr.rend()); int maj1_count = 0, maj2_count = 0; // Check if any of the the majority elements is really the majority for (const auto& itr: arr) { maj1_count += majority1 == itr ? 1 : 0; maj2_count += majority2 == itr ? 1 : 0; } if (maj1_count >= arr.size()/2) return majority1; if (maj2_count >= arr.size()/2) return majority2; // else return -1 return -1; } 

Codice testato qui

Grazie per le risposte precedenti che mi hanno ispirato a conoscere l’algo di Bob Boyer. 🙂

Versione generica Java: una versione modificata dell’algoritmo di Boyer

Nota: array di tipo primitivo potrebbe usare wrapper.

 import com.sun.deploy.util.ArrayUtil; import com.sun.tools.javac.util.ArrayUtils; /** * Created by yesimroy on 11/6/16. */ public class FindTheMajority { /** * * @param array * @return the value of the majority elements */ public static  E findTheMajority(E[] array){ E majority =null; int count =0; for(int i=0; i (array.length /2)){ return majority; }else{ return null; } } public static void main(String[] args){ String[] test_case1 = {"Roy","Roy","Roy","Ane","Dan","Dan","Ane","Ane","Ane","Ane","Ane"}; Integer[] test_case2 = {1,3,2,3,3,3,3,4,5}; System.out.println("test_case1_result:" + findTheMajority(test_case1)); System.out.println("test case1 the number of majority element should greater than" + test_case1.length/2); System.out.println(); System.out.println("test_case2_result:" + findTheMajority(test_case2)); System.out.println("test case2 the number of majority element should greater than" + test_case2.length/2); System.out.println(); } 

}

// Supponiamo di avere un array A. // Se abbiamo tutti gli elementi dell’array dato, ogni elemento è inferiore a K, allora possiamo creare un array addizionale B con lunghezza K + 1.

// Inizializza il valore in ogni indice dell’array con 0. // Quindi iterate attraverso l’array specificato A, per ogni valore dell’array A [i], incrementa il valore con 1 nell’indice corrispondente A [i] nell’array creato B.

// Dopo aver iterato attraverso l’array A, ora scorrere l’array B e trovare il valore massimo. Se trovi il valore maggiore di n / 2, restituisci quell’indice particolare.

// La complessità temporale sarà O (n + K) se K <= n quindi equivalente a O (n).

// Abbiamo un vincolo qui che tutti gli elementi dell’array sono O (K). // Supponendo che ogni elemento sia minore o uguale a 100, in questo caso K è 100.

 import javax.print.attribute.standard.Finishings; public class MajorityElement { private static int maxElement=100; //Will have all zero values initially private static int arrB[]=new int[maxElement+1]; static int findMajorityElement(int[] arrA) { int count = 0, i, majorityElement; int n=arrA.length; for (i = 0; i < n; i++) { arrB[arrA[i]]+=1; } int maxElementIndex=1; for (i = 2; i < arrB.length; i++){ if (arrB[i]>n/2) { maxElementIndex=i; break; } } return maxElementIndex; }` public static void main(String[] args) { int arr[]={2,6,3,2,2,3,2,2}; System.out.println(findMajorityElement(arr)); } } 

Questo ti aiuterà e se due elementi ripetono lo stesso numero di volte se non ne mostrerà nessuno.

 int findCandidate(int a[], int size) { int count,temp=0,i,j, maj; for (i = 0; i < size; i++) { count=0; for(j=i;jtemp) { temp=count; maj=i; } else if(count==temp) { maj=-1; } } return maj; } 

Ecco come lo faccio in C ++ usando vettoriale e multimap (JSON con tasti ripetuti).

 #include  #include  #include  #include  #include  using namespace std; vector  majorityTwoElement(vector  nums) { // declare variables multimap  nums_map; vector  ret_vec, nums_unique (nums); int count = 0; bool debug = false; try { // get vector of unique numbers and sort them sort(nums_unique.begin(), nums_unique.end()); nums_unique.erase(unique(nums_unique.begin(), nums_unique.end()), nums_unique.end()); // create map of numbers and their count for(size_t i = 0; i < nums_unique.size(); i++){ // get number int num = nums_unique.at(i); if (debug) { cout << "num = " << num << endl; } // get count of number count = 0; // reset count for(size_t j = 0; j < nums.size(); j++) { if (num == nums.at(j)) { count++; } } // insert number and their count into map (sorted in ascending order by default) if (debug) { cout << "num = " << num << "; count = " << count << endl; } nums_map.insert(pair (count, num)); } // print map if (debug) { for (const auto &p : nums_map) { cout << "nums_map[" << p.first << "] = " << p.second << endl; } } // create return vector if (!nums_map.empty()) { // get data auto it = prev(nums_map.end(), 1); auto it1 = prev(nums_map.end(), 2); int last_key = it->first; int second_last_key = it1->first; // handle data if (last_key == second_last_key) { // tie for repeat count ret_vec.push_back(it->second); ret_vec.push_back(it1->second); } else { // no tie ret_vec.push_back(it->second); } } } catch(const std::exception& e) { cerr << "e.what() = " << e.what() << endl; throw -1; } return ret_vec; } int main() { vector  nums = {2, 1, 2, 3, 4, 2, 1, 2, 2}; try { // get vector vector  result = majorityTwoElement(nums); // print vector for(size_t i = 0; i < result.size(); i++) { cout << "result.at(" << i << ") = " << result.at(i) << endl; } } catch(int error) { cerr << "error = " << error << endl; return -1; } return 0; } // g++ test.cpp // ./a.out 

Ordina l’array dato: O (nlogn).

Se la dimensione dell’array è 7, l’elemento di maggioranza si verifica atleast ceiling (7/2) = 4 volte nell’array.

Dopo che l’array è stato ordinato, significa che se l’elemento di maggioranza viene trovato per la prima volta nella posizione i, si trova anche nella posizione i + floor (7/2) (4 occorrenze).

Esempio: array dato A – {7,3,2,3,3,6,3}

Ordina l’array – {2,3,3,3,3,6,7}

L’elemento 3 si trova nella posizione 1 (indice della matrice a partire da 0.) Se la posizione 1 + 3 = 4 ° elemento è anche 3, significa che 3 è l’elemento di maggioranza.

se passiamo attraverso l’array dall’inizio …

confrontare la posizione 0 con la posizione 3, i diversi elementi 2 e 3. confrontare la posizione 1 con la posizione 4, lo stesso elemento. Abbiamo trovato la nostra partita di maggioranza!

Complessità – O (n)

Complessità temporale totale – O (n).