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)