logo

Algorytm głosowania większością Boyera-Moore'a

The Głosowanie Boyera-Moore'a Algorytm jest jednym z popularnych algorytmów optymalnych, który służy do znalezienia elementu większościowego spośród podanych elementów, które mają więcej niż N/2 wystąpień. Działa to doskonale w przypadku znalezienia elementu większościowego, który wymaga 2 przejść przez dane elementy, co działa w złożoności czasowej O(N) i złożoności przestrzennej O(1).

Przyjrzyjmy się algorytmowi i intuicji stojącej za jego działaniem na przykładzie –



 Input : {1,1,1,1,2,3,5} Output : 1 Explanation : 1 occurs more than 3 times. Input : {1,2,3} Output : -1>

Algorytm ten działa w oparciu o fakt, że jeśli element występuje więcej niż N/2 razy, oznacza to, że pozostałe elementy inne niż ten byłyby na pewno mniejsze niż N/2. Sprawdźmy zatem przebieg algorytmu.

  • Najpierw wybierz kandydata z danego zbioru elementów, jeśli jest taki sam jak element kandydujący, zwiększ liczbę głosów. W przeciwnym razie zmniejsz liczbę głosów, jeśli głosy wyniosą 0, wybierz inny nowy element jako nowego kandydata.

Intuicja stojąca za pracą:
Gdy elementy są takie same jak element kandydujący, liczba głosów jest zwiększana, natomiast w przypadku znalezienia innego elementu (innego niż element kandydujący) zmniejszamy liczbę. To w rzeczywistości oznacza, że ​​zmniejszamy priorytet zdolności wygrywającej wybranego kandydata, ponieważ wiemy, że jeśli kandydat jest w większości, występuje to więcej niż N/2 razy, a pozostałe elementy są mniejsze niż N/2. Stale zmniejszamy liczbę głosów, ponieważ znaleźliśmy inny element niż element kandydujący. Kiedy liczba głosów wynosi 0, oznacza to w rzeczywistości, że na różne elementy przypada taka sama liczba głosów, co nie powinno mieć miejsca w przypadku elementu stanowiącego element większościowy. Zatem element kandydujący nie może być większością, dlatego wybieramy obecny element jako kandydata i kontynuujemy to samo, aż wszystkie elementy zostaną ukończone. Ostateczny kandydat byłby naszym elementem większościowym. Sprawdzamy, korzystając z drugiego przejścia, czy jego liczba jest większa niż N/2. Jeśli to prawda, uważamy to za element większościowy.

Kroki wdrożenia algorytmu:
Krok 1 - Znajdź kandydata z większością –



  • Zainicjuj zmienną powiedz i ,głosy = 0, kandydat =-1
  • Przejdź przez tablicę za pomocą pętli for
  • Jeśli głosów = 0, Wybierz kandydat = arr[i] , robić głosów=1 .
  • w przeciwnym razie, jeśli bieżący element jest taki sam, jak głosy dodatkowe kandydata
  • w przeciwnym razie zmniejsz liczbę głosów.

Krok 2 - Sprawdź, czy kandydat ma więcej niż N/2 głosów –

  • Zainicjuj liczbę zmiennych = 0 i zwiększ liczbę, jeśli jest taka sama jak kandydat.
  • Jeżeli liczba wynosi>N/2, zwróć kandydata.
  • w przeciwnym razie zwróć -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 Zatem 1 jest elementem większościowym.>

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) powrót kandydata; zwróć -1; } int main() { int tablica[] = { 1, 1, 1, 1, 2, 3, 4 }; int n = rozmiar(tablica) / rozmiar(tablica[0]); int większość = znajdźWiększość(arr, n); cout<< ' The majority element is : ' << majority; return 0; }>

>

>

Jawa




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)) zwróć kandydata; zwróć -1; // Ostatnią pętlę for i krok instrukcji if można // pominąć, jeśli potwierdzono, że // element większościowy jest obecny w tablicy, po prostu zwróć kandydata // w takim przypadku } // Kod sterownika public static void main(String[ ] argumenty) { int tablica [] = { 1, 1, 1, 1, 2, 3, 4 }; int większość = znajdźWiększość(arr); System.out.println(' Elementem większościowym jest: ' + większość); } } // Autorem tego kodu jest Arnav Sharma>

>

>

Python3


selen



# 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#




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)) powrót kandydata; zwróć -1; // Ostatnią pętlę for i krok instrukcji if można // pominąć, jeśli potwierdzono, że // element większościowy jest obecny w tablicy, po prostu zwróć kandydata // w takim przypadku } // Kod sterownika public static void Main(String[ ] argumenty) { int []arr = { 1, 1, 1, 1, 2, 3, 4}; int większość = znajdźWiększość(arr); Console.Write(' Element większościowy to: ' + większość); } } // Ten kod jest dziełem 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)) zwróć kandydata; zwróć -1; // Ostatnią pętlę for i krok instrukcji if można // pominąć, jeśli potwierdzono, że // element większościowy jest obecny w tablicy, po prostu zwróć kandydata // w takim przypadku } // Kod sterownika var arr = [ 1, 1 , 1, 1, 2, 3, 4]; var większość = znajdźWiększość(arr); document.write(' Element większościowy to: ' + większość); // Ten kod został napisany przez shivanishinghss2110.>

>

>

Wyjście

metody listy Java
 The majority element is : 1>

Złożoność czasowa: O(n) (Dla dwóch przejść przez tablicę)
Złożoność przestrzeni: O(1)