Elemento di maggioranza con C ++

Sia N il numero di elementi in un vettore o in un array. L'elemento o il leader della maggioranza è l'elemento che si verifica più della metà delle volte di tutti gli elementi del vettore. Metà di n significa: se n è 10, allora metà del tempo è 5. L'elemento a metà della posizione è all'indice 4, per il conteggio dell'indice basato su zero. Il minimo intero che è più della metà di 10 è chiaramente 6 (corrispondente all'indice 5). Se n è 11, la metà di N è considerata ancora 5. Questo è l'intero numero preso quando 11 è diviso per 2. L'indice per metà è ancora 4 per indicizzazione basata su zero. Quando n è 11, il minimo numero intero che è chiaramente più della metà letterale di 11 è ancora 6 (corrispondente all'indice 5).

Quindi, metà della lunghezza (dimensione) di un vettore è il risultato della divisione intera di n di 2. Cioè, l'intero numero del quoziente, dopo aver diviso per 2, viene preso se esiste o meno un resto.

L'elemento o il leader della maggioranza è l'elemento che si verifica più della metà delle volte di tutti gli elementi del vettore o dell'array. Dev'essere Di più della metà delle volte e non solo la metà dei tempi. Cioè, deve essere più di n/2 volte (prendendo il numero intero risultante). La funzione dovrebbe restituire -1, se non esiste alcun elemento di maggioranza.

Questo articolo spiega come determinare l'elemento di maggioranza per una complessità temporale di O (N). Cioè, sono necessari un massimo di n operazioni principali per ottenere l'elemento di maggioranza.

Esempi vettoriali

Considera il seguente vettore:

vettore A = 6, 8, 4, 6, 8, 6, 6

L'elemento di maggioranza (leader) è 6. Si verifica 4 volte su 7 volte (elementi).

Considera il seguente vettore:

vettore B = 3, 4, 3, 2, 3, -1, 3, 3

L'elemento di maggioranza è 3. Si verifica 5 volte su 8 elementi.

Considera il seguente vettore:

vettore C = 4, 3, 4, 4, 4, 2

L'elemento di maggioranza è 4. Si verifica 4 volte su 6 elementi.

Considera il seguente vettore:

vettore D = 5, 4, 7, 1, 7, 2, 3, 7, 8

Non esiste un elemento di maggioranza qui. Quindi, la funzione deve restituire -1. Ci sono nove elementi qui. Il numero, 7, si verifica tre volte e ciascuno degli altri elementi si verificano una volta. Tre non sono più della metà di nove. Un elemento a maggioranza accettabile avrebbe dovuto verificarsi, almeno 5 volte.

Illustrazione per algoritmo per O (n) complessità del tempo

Dai seguenti vettori, due elementi diversi vengono rimossi contemporaneamente.

Considera di nuovo il vettore:

vettore A = 6, 8, 4, 6, 8, 6, 6

L'elemento leader (maggioranza) è 6. I primi due elementi sono diversi. Se entrambi vengono rimossi, il set rimanente sarebbe, 4, 6, 8, 6, 6. In questo set rimanente, 6 è ancora il leader: tre volte su 5 volte. I prossimi due elementi, 4 e 6 sono diversi. Se vengono rimossi, il set rimanente sarà 8, 6, 6. Nel set rimanente, 6 è ancora il leader. I prossimi due elementi, 8 e 6 sono diversi. Se vengono rimossi, il set rimanente sarà 6. In quest'ultima serie di un solo elemento, 6 è ancora il leader. Sembra quindi che due numeri diversi vengano rimossi ripetutamente. L'elemento rimanente finale sarebbe l'elemento di maggioranza.

Considera ora il vettore:

vettore B = 3, 4, 3, 2, 3, -1, 3, 3

L'elemento leader (maggioranza) è 3. I primi due elementi sono diversi. Se entrambi vengono rimossi, il set rimanente sarebbe, 3, 2, 3, -1, 3, 3. In questo set rimanente, 3 è ancora il leader: quattro volte su sei volte. I prossimi due elementi, 3 e 2 sono diversi. Se vengono rimossi, il set rimanente sarà 3, -1, 3, 3. Nel set rimanente, 3 è ancora il leader. I prossimi due elementi, 3 e -1 sono diversi. Se vengono rimossi, il set rimanente sarà 3, 3. In quest'ultima serie di due elementi, 3 è ancora il leader. Quindi sembra ancora che due numeri diversi vengano rimossi ripetutamente. Gli stessi elementi finali rimanenti sarebbero l'elemento di maggioranza.

Considera il prossimo vettore:

vettore C = 4, 3, 4, 4, 4, 2

L'elemento leader (maggioranza) è 4. I primi due elementi sono diversi. Se entrambi vengono rimossi, il set rimanente sarebbe, 4, 4, 4, 2. In questo set rimanente, 4 è ancora il leader: tre volte su quattro volte. I prossimi due elementi, 4 e 4 sono uguali e non dovrebbero essere rimossi. Tuttavia, il primo elemento qui, e il terzo elemento qui, può essere considerato per la rimozione. Succede che anche questi due siano gli stessi. Tuttavia, il primo elemento e il quarto elemento possono essere considerati per la rimozione. Sono diversi, quindi vengono rimossi. L'ultimo set rimanente è 4, 4. Quindi sembra ancora che due numeri diversi vengano rimossi ripetutamente. Gli stessi elementi finali rimanenti sarebbero l'elemento di maggioranza.

Considera quindi il vettore:

vettore D = 5, 4, 7, 1, 7, 2, 3, 7, 8

Sappiamo già che questo vettore non ha leader, anche se 7 si verificano tre volte e il numero si verifica una volta. 7 avviene tre su nove volte e questo non lo rende un leader. Tuttavia, diverse coppie possono essere rimosse ripetutamente per vedere come sarebbe il set rimanente finale. I primi due elementi, 5 e 4 sono diversi. Se vengono rimossi, il set rimanente sarebbe, 7, 1, 7, 2, 3, 7, 8. In questo set rimanente, 7 è ancora l'elemento predominante. Ma non è ancora il leader del set rimanente. Ricorda che il leader deve avvenire più della metà del numero di volte. I prossimi due elementi, 7 e 1 sono diversi. Se vengono rimossi, il set rimanente sarebbe 7, 2, 3, 7, 8. 7 è ancora l'elemento predominante, ma non è ancora il leader. I prossimi due elementi, 7 e 2 sono diversi. Vengono rimossi per avere il set, 3, 7, 8. Questa volta non è rimasto alcun elemento predominante e non c'è leader. I prossimi due elementi, 3 e 7 sono diversi. Quando vengono rimossi, il set rimanente sarebbe 8.

Per i tre vettori precedenti, l'elemento rimanente finale o gli stessi elementi rimanenti finali è l'elemento di maggioranza. È già noto che in quest'ultimo vettore non esiste un elemento di maggioranza. Quindi, il fatto che un elemento rimanga finalmente non significa necessariamente che sia l'elemento di maggioranza.

Ora, considera il caso in cui n è un numero pari e ogni elemento nel vettore si verifica una volta. In questo caso, tutte le coppie di elementi verranno rimosse e non ci sarà alcun elemento nel set finale. Chiaramente, in questo caso, la funzione deve restituire -1 in quanto non esiste un elemento di maggioranza.

Per l'ultimo elemento rimanente o gli stessi elementi rimanenti finali hanno/devono essere verificati se l'elemento si verifica più della metà del numero di volte nel vettore. Questo elemento rimanente è chiamato candidato.

O (N) Algoritmo di complessità del tempo per l'elemento di maggioranza

La strategia deve rimuovere coppie di elementi che sono diversi, ripetutamente: a partire dalla sinistra nel vettore dato. Se nessun elemento rimane, allora non esiste un elemento di maggioranza e la funzione dovrebbe restituire -1. Se ne rimangono uno o più degli stessi elementi, deve essere verificato se l'elemento si verifica più della metà dei tempi nel vettore. Questo elemento è chiamato candidato. Diventa l'elemento di maggioranza se si verifica più della metà del numero di volte.

Questo controllo può essere effettuato in tempo lineare, scansionando il vettore da sinistra e per fermarsi non appena il numero di occorrenza è appena maggiore della metà della lunghezza del vettore. Se l'intero vettore viene scansionato e il numero di volte in cui si verifica il candidato non è più della metà dei tempi, allora non esiste un elemento di maggioranza (secondo la definizione).

Strategia con c++

Con C ++, gli elementi non devono essere rimossi dal vettore dato. Invece, viene utilizzato uno stack. Il primo elemento del vettore viene spinto nella parte superiore dello stack. Se l'elemento successivo è diverso dall'elemento superiore nello stack, l'elemento superiore nello stack viene rimosso (spuntato); Altrimenti, questo prossimo elemento viene spinto nella parte superiore dello stack (se l'elemento superiore dello stack e questo elemento successivo, sono uguali). Questo schema continua per il resto degli elementi.

Alla fine della scansione (un passaggio del vettore), se nessun elemento è nello stack, non esiste un elemento di maggioranza. Uno o più elementi possono rimanere nello stack. Se rimane più di un elemento nello stack, questi elementi rimanenti devono essere gli stessi. Questo elemento è chiamato candidato.

Se uno o più dello stesso elemento rimangono nello stack, quell'elemento o lo stesso elemento che si verifica più di una volta è un possibile elemento di maggioranza. Il vettore deve essere ri-scansione per vedere se questo elemento si verifica più della metà del numero di volte per il numero totale di elementi nel vettore. Se si verifica più della metà dei tempi, quell'elemento è l'elemento di maggioranza (leader); Altrimenti, il vettore (o l'array) non ha elementi maggioritari (la funzione dovrebbe restituire -1).

Coding C ++

Ogni volta che un vettore viene utilizzato in un programma C ++, l'intestazione del programma deve essere qualcosa di simile:

#includere
#includere
#includere
Utilizzo dello spazio dei nomi std;

La biblioteca dello stack deve essere inclusa. Viene utilizzato lo spazio dei nomi standard. Vector è l'elenco principale, quindi la sua libreria è inclusa. La libreria iostream dovrebbe essere sempre inclusa; È responsabile per l'input/output. Il nome della funzione per l'algoritmo O (N) è la maggioranza. La prima metà del codice funzione è:

int maggiorityElement (vettore &UN)
int n = a.misurare();
int size = 0;
pila St;
st.push (a [0]);
per (int i = 1; iSe (st.size ()> 0) // per evitare, errore di errore di segmentazione (dumped core)
if (a [i] == st.superiore())
st.push (a [i]);

altro
st.pop(); //se differente


altro
st.push (a [i]); // spingi sulla parte superiore dello stack se vuoto

Questo ha il primo per loop che è il principale per loop. Prima del per loop, il primo elemento del vettore viene inviato allo stack (la parte superiore). Questo per loop implementa la strategia C ++ è menzionata sopra. La seconda e ultima parte della funzione maggioranzaelement () è:

int candidato = -1;
Se (st.size ()> 0)
candidato = st.superiore();
int leader = -1;
int count = 0;
per (int i = 0; iif (a [i] == candidato)
conta += 1;


if (count> n/2)
leader = candidato;
leader di ritorno;

Questo controlla se il candidato è effettivamente l'elemento di maggioranza. Il leader variabile è sinonimo dell'elemento di maggioranza. Il candidato variabile è il possibile elemento di maggioranza. Non appena il valore per il conteggio supera N/2, il candidato è l'elemento di maggioranza. Questa parte ha il per loop che controlla se il vettore ha un elemento di maggioranza. Le due parti sopra devono essere unite per formare una funzione. La funzione restituisce -1, se non esiste alcun elemento di maggioranza.

Una funzione principale C ++ adatta, per il codice sopra è:

vettore v1 = 6, 8, 4, 6, 8, 6, 6;
int ret1 = maggioranzaelement (V1);
cout << ret1 << endl;
vettore v2 = 3, 4, 3, 2, 3, -1, 3, 3;
int ret2 = maggioranzaelement (V2);
cout << ret2 << endl;
vettore v3 = 4, 3, 4, 4, 4, 2;
int ret3 = maggioranzaelement (V3);
cout << ret3 << endl;
vettore v4 = 5, 4, 7, 1, 7, 2, 3, 7, 8;
int ret4 = maggioranzaelement (V4);
cout << ret4 << endl;
restituzione 0;

Complessità temporale

Poiché ci sono due per loop con il vettore che viene scansionato due volte, il lettore potrebbe essere tentato di dire che la complessità del tempo è, O (n+N). Ora, il corpo del primo per loop è molto più lungo del corpo per il secondo per loop. Quindi, il tempo da eseguire per il secondo corpo per loop è molto più piccolo del tempo per il primo corpo per loop da eseguire. In altre parole, quel tempo per il secondo corpo è relativamente trascurabile. Quindi, la complessità del tempo per l'algoritmo di cui sopra è citata come:

SU)

La complessità del tempo è il numero approssimativo di operazioni principali per la funzione in questione.

Conclusione

La strategia generale per trovare l'elemento di maggioranza in o (n) il tempo deve rimuovere coppie di elementi che sono diversi, ripetutamente, a partire dalla sinistra nell'elenco dato. Se nessun elemento rimane, infine nell'elenco, allora non esiste un elemento di maggioranza e la funzione dovrebbe restituire -1. Se uno o più dello stesso elemento rimangono, allora deve essere verificato se l'elemento si verifica più della metà delle volte nell'elenco. Questo elemento è chiamato candidato. Se il candidato si verifica più della metà dei tempi, nell'elenco indicato, allora il candidato è l'elemento di maggioranza.

Chrys