The Boyer-Moore äänestää Algoritmi on yksi suosituimmista optimaalisista algoritmeista, jota käytetään löytämään enemmistöelementti annetuista elementeistä, joilla on enemmän kuin N/2 esiintymää. Tämä toimii täydellisesti enemmistöelementin löytämisessä, joka kulkee 2 kertaa annettujen elementtien yli, mikä toimii O(N) aikakompleksisuudessa ja O(1) avaruuskompleksisuudessa.
Katsotaanpa sen toiminnan takana olevaa algoritmia ja intuitiota ottamalla esimerkki -
Input : {1,1,1,1,2,3,5} Output : 1 Explanation : 1 occurs more than 3 times. Input : {1,2,3} Output : -1> Tämä algoritmi toimii siinä tosiasiassa, että jos jokin elementti esiintyy enemmän kuin N/2 kertaa, se tarkoittaa, että muut kuin tämä elementit olisivat ehdottomasti pienempiä kuin N/2. Tarkastetaan siis algoritmin etenemistä.
- Valitse ensin ehdokas annetusta elementtijoukosta, jos se on sama kuin ehdokaselementti, lisää ääniä. Muussa tapauksessa vähennä ääniä, jos äänistä tulee 0, valitse uudeksi ehdokkaaksi toinen uusi elementti.
Intuitio työn takana:
Kun elementit ovat samat kuin ehdokaselementti, ääniä kasvatetaan, kun taas jos jokin muu elementti löytyy (ei yhtä suuri kuin ehdokaselementti), vähennimme määrää. Tämä tarkoittaa itse asiassa sitä, että vähennämme valitun ehdokkaan voittokyvyn prioriteettia, koska tiedämme, että jos ehdokas on enemmistössä, se esiintyy enemmän kuin N/2 kertaa ja loput elementit ovat pienempiä kuin N/2. Jatkamme äänten vähentämistä, koska löysimme eri elementtejä kuin ehdokaselementti. Kun äänistä tulee 0, tämä tarkoittaa itse asiassa, että eri elementeillä on yhtä monta ääntä, minkä ei pitäisi olla, jos elementti on enemmistöelementti. Ehdokaselementti ei siis voi olla enemmistö, joten valitsemme ehdokkaaksi nykyisen elementin ja jatkamme samalla tavalla, kunnes kaikki elementit ovat valmiit. Lopullinen ehdokas olisi enemmistöelementtimme. Tarkistamme käyttämällä 2. läpikulkua nähdäksemme, onko sen määrä suurempi kuin N/2. Jos se on totta, pidämme sitä enemmistönä.
Vaiheet algoritmin toteuttamiseksi:
Vaihe 1 - Etsi ehdokas, jolla on enemmistö
- Alusta muuttuva sanonta i ,äänet = 0, ehdokas =-1
- Kulje taulukon läpi käyttämällä for-silmukkaa
- Jos äänet = 0, Valitse ehdokas = arr[i] , tee äänet = 1 .
- muuten, jos nykyinen elementti on sama kuin ehdokas lisää ääniä
- muuten vähennä ääniä.
Vaihe 2 – Tarkista, onko ehdokkaalla enemmän kuin N/2 ääntä –
- Alusta muuttujan määrä =0 ja lisää määrää, jos se on sama kuin ehdokas.
- Jos luku on>N/2, palauta ehdokas.
- muuten paluu -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 Joten 1 on enemmistöelementti.>
C++
paikallinen java
// 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) paluuehdokas; paluu -1; } int main() { int arr[] = { 1, 1, 1, 1, 2, 3, 4 }; int n = koko(arr) / koko(arr[0]); int enemmistö = findMajority(arr, n); cout<< ' The majority element is : ' << majority; return 0; }> |
>
>
Java
heittää merkkijono int javaan
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)) paluuehdokas; paluu -1; // Viimeinen for-silmukka ja if-lauseen vaihe voidaan // ohittaa, jos enemmistöelementin vahvistetaan // olevan läsnä taulukossa vain palauttaa ehdokkaan // siinä tapauksessa } // Ohjainkoodi public static void main(String[ ] args) { int arr[] = { 1, 1, 1, 1, 2, 3, 4 }; int enemmistö = findMajority(arr); System.out.println(' Enemmistöelementti on ' + enemmistö); } } // Tämän koodin tarjoaa Arnav Sharma> |
>
>
Python 3
# 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> |
concat merkkijonot java
>
>
milloin ensimmäinen tietokone keksittiin
C#
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>(nums.Length / 2)) paluuehdokas; paluu -1; // Viimeinen for-silmukka ja if-lauseen vaihe voidaan // ohittaa, jos enemmistöelementin vahvistetaan // olevan läsnä taulukossa vain palauttaa ehdokkaan // siinä tapauksessa } // Ohjainkoodi public static void Main(String[ ] args) { int []arr = { 1, 1, 1, 1, 2, 3, 4}; int enemmistö = findMajority(arr); Console.Write(' Enemmistöelementti on ' + enemmistö); } } // Tämän koodin on tuottanut shivanisinghss2110> |
>
>
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)) paluuehdokas; paluu -1; // Viimeinen for-silmukka ja if-lauseen vaihe voidaan // ohittaa, jos enemmistöelementin vahvistetaan // olevan läsnä taulukossa vain palauttaa ehdokkaan // siinä tapauksessa } // Ohjainkoodi var arr = [ 1, 1 , 1, 1, 2, 3, 4]; var enemmistö = findMajority(arr); document.write(' Enemmistöelementti on ' + enemmistö); // Tämän koodin tarjoaa shivanisinghss2110.>> |
>bubble sort javaThe majority element is : 1>
Aika monimutkaisuus: O(n) (Kahdelle siirrolle taulukon yli)
Tilan monimutkaisuus: O(1)