Der Boyer-Moore-Abstimmung Der Algorithmus ist einer der beliebtesten optimalen Algorithmen, der verwendet wird, um das Mehrheitselement unter den gegebenen Elementen zu finden, die mehr als N/2 Vorkommen haben. Dies funktioniert einwandfrei, um das Mehrheitselement zu finden, das zwei Durchläufe über die gegebenen Elemente erfordert, was bei O(N)-Zeitkomplexität und O(1)-Raumkomplexität funktioniert.
Lassen Sie uns den Algorithmus und die Intuition hinter seiner Funktionsweise anhand eines Beispiels sehen:
Input : {1,1,1,1,2,3,5} Output : 1 Explanation : 1 occurs more than 3 times. Input : {1,2,3} Output : -1> Dieser Algorithmus basiert auf der Tatsache, dass, wenn ein Element mehr als N/2-mal vorkommt, dies bedeutet, dass die restlichen Elemente außer diesem definitiv weniger als N/2 sein würden. Lassen Sie uns also die Vorgehensweise des Algorithmus überprüfen.
- Wählen Sie zunächst einen Kandidaten aus der angegebenen Menge von Elementen aus. Wenn dieser mit dem Kandidatenelement übereinstimmt, erhöhen Sie die Stimmen. Andernfalls verringern Sie die Stimmen, wenn die Stimmen 0 werden, und wählen Sie ein anderes neues Element als neuen Kandidaten aus.
Intuition hinter der Arbeit:
Wenn die Elemente mit dem Kandidatenelement identisch sind, werden die Stimmen erhöht, während wir die Anzahl verringert haben, wenn ein anderes Element gefunden wird (nicht gleich dem Kandidatenelement). Dies bedeutet tatsächlich, dass wir die Priorität der Gewinnfähigkeit des ausgewählten Kandidaten herabsetzen, da wir wissen, dass, wenn der Kandidat die Mehrheit hat, dies mehr als N/2 Mal vorkommt und die verbleibenden Elemente weniger als N/2 sind. Wir reduzieren die Stimmen weiter, da wir einige andere Elemente als das Kandidatenelement gefunden haben. Wenn die Stimmen 0 werden, bedeutet dies tatsächlich, dass es für verschiedene Elemente die gleiche Anzahl an Stimmen gibt, was nicht der Fall sein sollte, wenn das Element das Mehrheitselement ist. Das Kandidatenelement kann also nicht die Mehrheit sein und daher wählen wir das aktuelle Element als Kandidaten und machen so weiter, bis alle Elemente fertig sind. Der endgültige Kandidat wäre unser Mehrheitselement. Wir prüfen anhand der 2. Durchquerung, ob die Anzahl größer als N/2 ist. Wenn es wahr ist, betrachten wir es als das Mehrheitselement.
Schritte zur Implementierung des Algorithmus:
Schritt 1 - Finden Sie einen Kandidaten mit der Mehrheit –
- Initialisieren Sie beispielsweise eine Variable i ,Stimmen = 0, Kandidat =-1
- Durchlaufen Sie das Array mit der for-Schleife
- Wenn Stimmen = 0, wählen Sie das Kandidat = arr[i] , machen Stimmen=1 .
- Andernfalls, wenn das aktuelle Element mit den Stimmen des Kandidaten übereinstimmt
- andernfalls dekrementieren Sie die Stimmen.
Schritt 2 - Prüfen Sie, ob der Kandidat mehr als N/2 Stimmen hat –
- Initialisieren Sie eine Variable count =0 und erhöhen Sie count, wenn sie mit dem Kandidaten übereinstimmt.
- Wenn die Anzahl> N/2 ist, wird der Kandidat zurückgegeben.
- sonst wird -1 zurückgegeben.
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 Also ist 1 das Mehrheitselement.>
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) Rückkehrkandidat; return -1; } int main() { int arr[] = { 1, 1, 1, 1, 2, 3, 4 }; int n = sizeof(arr) / sizeof(arr[0]); int Majorität = findMajority(arr, n); cout<< ' The majority element is : ' << majority; return 0; }> |
>
>
Java
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)) Return Candidate; return -1; // Die letzte for-Schleife und der if-Anweisungsschritt können // übersprungen werden, wenn bestätigt wird, dass // ein Mehrheitselement in einem Array vorhanden ist. Geben Sie einfach den Kandidaten zurück // in diesem Fall } // Treibercode public static void main(String[ ] args) { int arr[] = { 1, 1, 1, 1, 2, 3, 4 }; int Majorität = findMajority(arr); System.out.println(' Das Mehrheitselement ist: ' + Mehrheit); } } // Dieser Code wurde von Arnav Sharma beigesteuert> |
>
>
Python3
Formatieren Sie ein Datum in Java
# 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)) Return Candidate; return -1; // Die letzte for-Schleife und der if-Anweisungsschritt können // übersprungen werden, wenn bestätigt wird, dass ein Mehrheitselement // in einem Array vorhanden ist. Geben Sie einfach den Kandidaten zurück. // In diesem Fall } // Treibercode public static void Main(String[ ] args) { int []arr = { 1, 1, 1, 1, 2, 3, 4}; int Majorität = findMajority(arr); Console.Write(' Das Mehrheitselement ist: ' + Mehrheit); } } // Dieser Code wurde von shivanisinghss2110>'> beigesteuert |
>
>// 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)) Return Candidate; return -1; // Die letzte for-Schleife und der if-Anweisungsschritt können // übersprungen werden, wenn bestätigt wird, dass ein Mehrheitselement // in einem Array vorhanden ist. Geben Sie einfach den Kandidaten zurück. // In diesem Fall } // Treibercode var arr = [ 1, 1 , 1, 1, 2, 3, 4 ]; var Majorität = findMajority(arr); document.write(' Das Mehrheitselement ist: ' + Mehrheit); // Dieser Code wurde von shivanisinghss2110 beigesteuert.>>>AusgabeThe majority element is : 1>Zeitkomplexität: O(n) (Für zwei Durchgänge über das Array)
Raumkomplexität: O(1)