IL Votazione Boyer-Moore L'algoritmo è uno dei popolari algoritmi ottimali che viene utilizzato per trovare l'elemento maggioritario tra gli elementi dati che hanno più di N/2 occorrenze. Funziona perfettamente per trovare l'elemento maggioritario che effettua 2 attraversamenti sugli elementi dati, che funziona con complessità temporale O (N) e complessità spaziale O (1).
Vediamo l'algoritmo e l'intuizione dietro il suo funzionamento, facendo un esempio:
Input : {1,1,1,1,2,3,5} Output : 1 Explanation : 1 occurs more than 3 times. Input : {1,2,3} Output : -1> Questo algoritmo funziona sul fatto che se un elemento ricorre più di N/2 volte, significa che gli elementi rimanenti diversi da questo sarebbero sicuramente inferiori a N/2. Controlliamo quindi il procedimento dell'algoritmo.
- Innanzitutto, scegli un candidato dall'insieme di elementi fornito se è uguale all'elemento candidato, aumenta i voti. Altrimenti diminuisci i voti se i voti diventano 0, seleziona un altro nuovo elemento come nuovo candidato.
L'intuizione dietro il lavoro:
Quando gli elementi sono uguali all'elemento candidato, i voti vengono incrementati mentre quando viene trovato qualche altro elemento (non uguale all'elemento candidato), si diminuisce il conteggio. Ciò significa in realtà che stiamo diminuendo la priorità di capacità di vincita del candidato selezionato, poiché sappiamo che se il candidato è in maggioranza ciò si verifica più di N/2 volte e gli elementi rimanenti sono inferiori a N/2. Continuiamo a diminuire i voti poiché abbiamo trovato alcuni elementi diversi rispetto all'elemento candidato. Quando i voti diventano 0, ciò significa in realtà che esiste lo stesso numero di voti per diversi elementi, il che non dovrebbe essere il caso affinché l'elemento sia l'elemento di maggioranza. Quindi l'elemento candidato non può essere la maggioranza e quindi scegliamo l'elemento presente come candidato e continuiamo così finché tutti gli elementi non sono finiti. Il candidato finale sarebbe il nostro elemento di maggioranza. Controlliamo utilizzando il 2° attraversamento per vedere se il suo conteggio è maggiore di N/2. Se è vero, lo consideriamo come l'elemento maggioritario.
Passaggi per implementare l'algoritmo:
Passo 1 - Trovare un candidato con la maggioranza –
esempio di codice Java
- Inizializza una variabile, ad esempio i ,voti = 0, candidato =-1
- Attraversa l'array utilizzando il ciclo for
- Se voti = 0, scegli il candidato = arr[i] , Fare voti=1 .
- altrimenti se l'elemento corrente è lo stesso del candidato incrementa i voti
- altrimenti diminuisci i voti.
Passo 2 - Controlla se il candidato ha più di N/2 voti –
- Inizializza una variabile count =0 e incrementa count se è uguale al candidato.
- Se il conteggio è>N/2, restituire il candidato.
- altrimenti restituisce -1.
Dry run for the above example: Given : arr[]= 1 1 1 1 2 3 5 votes =0 1 2 3 4 3 2 1 candidate = -1 1 1 1 1 1 1 1 candidate = 1 after first traversal 1 1 1 1 2 3 5 count =0 1 2 3 4 4 4 4 candidate = 1 Hence count>7/2 =3 Quindi 1 è l'elemento maggioritario.>
C++
// C++ implementation for the above approach> #include> using> namespace> std;> // Function to find majority element> int> findMajority(>int> arr[],>int> n)> {> >int> i, candidate = -1, votes = 0;> >// Finding majority candidate> >for> (i = 0; i if (votes == 0) { candidate = arr[i]; votes = 1; } else { if (arr[i] == candidate) votes++; else votes--; } } int count = 0; // Checking if majority candidate occurs more than n/2 // times for (i = 0; i if (arr[i] == candidate) count++; } if (count>n/2) candidato di ritorno; ritorno -1; } int main() { int arr[] = { 1, 1, 1, 1, 2, 3, 4 }; int n = dimensioneof(arr) / dimensioneof(arr[0]); int maggioranza = findMajority(arr, n); cout<< ' The majority element is : ' << majority; return 0; }> |
>
>
Giava
Android può giocare a GamePigeon
import> java.io.*;> class> GFG> {> >// Function to find majority element> >public> static> int> findMajority(>int>[] nums)> >{> >int> count =>0>, candidate = ->1>;> >// Finding majority candidate> >for> (>int> index =>0>; index if (count == 0) { candidate = nums[index]; count = 1; } else { if (nums[index] == candidate) count++; else count--; } } // Checking if majority candidate occurs more than // n/2 times count = 0; for (int index = 0; index if (nums[index] == candidate) count++; } if (count>(nums.length/2)) ritorna candidato; ritorno -1; // L'ultimo ciclo for e il passaggio dell'istruzione if possono // essere saltati se viene confermato che un elemento maggioritario // è presente in un array, è sufficiente restituire il candidato // in tal caso } // Codice driver public static void main(String[ ] argomenti) { int arr[] = { 1, 1, 1, 1, 2, 3, 4 }; int maggioranza = findMajority(arr); System.out.println(' L'elemento di maggioranza è: ' + maggioranza); } } // Questo codice è stato fornito da Arnav Sharma> |
>
>
Python3
# Python implementation for the above approach> # Function to find majority element> def> findMajority(arr, n):> >candidate>=> ->1> >votes>=> 0> > ># Finding majority candidate> >for> i>in> range> (n):> >if> (votes>=>=> 0>):> >candidate>=> arr[i]> >votes>=> 1> >else>:> >if> (arr[i]>=>=> candidate):> >votes>+>=> 1> >else>:> >votes>->=> 1> >count>=> 0> > ># Checking if majority candidate occurs more than n/2> ># times> >for> i>in> range> (n):> >if> (arr[i]>=>=> candidate):> >count>+>=> 1> > >if> (count>n>/>/> 2>):> >return> candidate> >else>:> >return> ->1> # Driver Code> arr>=> [>1>,>1>,>1>,>1>,>2>,>3>,>4> ]> n>=> len>(arr)> majority>=> findMajority(arr, n)> print>(>' The majority element is :'> ,majority)> > # This code is contributed by shivanisinghss2110> |
>
>
C#
metodo sottostringa java
using> System;> class> GFG> {> >// Function to find majority element> >public> static> int> findMajority(>int>[] nums)> >{> >int> count = 0, candidate = -1;> >// Finding majority candidate> >for> (>int> index = 0; index if (count == 0) { candidate = nums[index]; count = 1; } else { if (nums[index] == candidate) count++; else count--; } } // Checking if majority candidate occurs more than // n/2 times count = 0; for (int index = 0; index if (nums[index] == candidate) count++; } if (count>(num.Lunghezza/2)) ritorna candidato; ritorno -1; // L'ultimo ciclo for e il passaggio dell'istruzione if possono // essere saltati se viene confermato che un elemento maggioritario // è presente in un array, è sufficiente restituire il candidato // in tal caso } // Codice driver public static void Main(String[ ] argomenti) { int []arr = { 1, 1, 1, 1, 2, 3, 4}; int maggioranza = findMajority(arr); Console.Write(' L'elemento di maggioranza è: ' + maggioranza); } } // Questo codice è un contributo di shivanisinghss2110> |
>
come convertire int in stringa java
>
Javascript
> // Function to find majority element> function> findMajority(nums)> >{> >var> count = 0, candidate = -1;> >// Finding majority candidate> >for> (>var> index = 0; index if (count == 0) { candidate = nums[index]; count = 1; } else { if (nums[index] == candidate) count++; else count--; } } // Checking if majority candidate occurs more than // n/2 times count = 0; for (var index = 0; index if (nums[index] == candidate) count++; } if (count>(nums.length/2)) ritorna candidato; ritorno -1; // L'ultimo ciclo for e il passaggio dell'istruzione if possono // essere saltati se viene confermato che un elemento maggioritario // è presente in un array, è sufficiente restituire il candidato // in tal caso } // Codice driver var arr = [ 1, 1 , 1, 1, 2, 3, 4]; var maggioranza = findMajority(arr); document.write(' L'elemento di maggioranza è: ' + maggioranza); // Questo codice è fornito da shivanisinghss2110.> |
>
>Produzione
The majority element is : 1>
Complessità temporale: O(n) (Per due passaggi sull'array)
Complessità spaziale: O(1)