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)