The Голосування Боєра-Мура Алгоритм — один із популярних оптимальних алгоритмів, який використовується для знаходження мажоритарного елемента серед даних елементів, які мають більше ніж N/2 входжень. Це чудово працює для пошуку основного елемента, який виконує 2 обходи над заданими елементами, що працює з O(N) часовою складністю та O(1) просторовою складністю.
Давайте розглянемо алгоритм та інтуїцію, що стоїть за його роботою, на прикладі –
Input : {1,1,1,1,2,3,5} Output : 1 Explanation : 1 occurs more than 3 times. Input : {1,2,3} Output : -1> Цей алгоритм працює на тому факті, що якщо елемент зустрічається більше ніж N/2 разів, це означає, що решта елементів, окрім цього, точно буде меншою ніж N/2. Отже, перевіримо роботу алгоритму.
- Спочатку виберіть кандидата з заданого набору елементів, якщо він збігається з елементом кандидата, збільште голоси. В іншому випадку зменшіть кількість голосів, якщо голосів стане 0, виберіть інший новий елемент як нового кандидата.
Інтуїція за роботою:
Коли елементи збігаються з елементом-кандидатом, голоси збільшуються, тоді як коли знайдено інший елемент (не рівний елементу-кандидату), ми зменшуємо підрахунок. Це фактично означає, що ми знижуємо пріоритет переможної здатності вибраного кандидата, оскільки ми знаємо, що якщо кандидат має більшість, це відбувається більше ніж N/2 разів, а решта елементів менше ніж N/2. Ми продовжуємо зменшувати кількість голосів, оскільки знайшли елементи, відмінні від елементів кандидата. Коли голоси стають нульовими, це фактично означає, що існує однакова кількість голосів для різних елементів, чого не повинно бути, щоб елемент був мажоритарним. Отже, елемент-кандидат не може бути більшістю, тому ми обираємо поточний елемент як кандидата і продовжуємо те саме, доки всі елементи не будуть закінчені. Остаточним кандидатом буде наша більшість. Ми перевіряємо, використовуючи 2-й обхід, щоб побачити, чи його кількість перевищує N/2. Якщо це правда, ми вважаємо це мажоритарним елементом.
Етапи реалізації алгоритму:
Крок 1 - Знайти кандидата з більшістю –
- Ініціалізація змінної say i ,голосів = 0, кандидат =-1
- Перейдіть по масиву за допомогою циклу for
- Якщо голосів = 0, вибрати кандидат = arr[i] , зробити голосів=1 .
- інакше, якщо поточний елемент збігається з приростом голосів кандидата
- інакше зменшити кількість голосів.
Крок 2 – Перевірте, чи має кандидат більше N/2 голосів –
- Ініціалізуйте змінну count =0 і збільште кількість, якщо вона збігається з кандидатом.
- Якщо кількість>N/2, поверніть кандидата.
- інакше повертає -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 Отже, 1 є основним елементом.>
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>п/2) повернення кандидата; повернення -1; } int main() { int arr[] = { 1, 1, 1, 1, 2, 3, 4 }; int n = sizeof(arr) / sizeof(arr[0]); int більшість = 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)) повернути кандидата; повернення -1; // Останній цикл for і крок оператора if можна // пропустити, якщо підтверджено, що основний елемент // присутній у масиві, // у цьому випадку повертає кандидата } // Код драйвера public static void main(String[ ] args) { int arr[] = { 1, 1, 1, 1, 2, 3, 4 }; int більшість = findMajority(arr); System.out.println(' Елемент більшості: ' + більшість); } } // Цей код надав Арнав Шарма> |
>
js onclick
>
Python3
# 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)) повернути кандидата; повернення -1; // Останній цикл for і крок оператора if можна // пропустити, якщо підтверджено, що основний елемент // присутній в масиві, // у цьому випадку повертає кандидата } // Код драйвера public static void Main(String[ ] args) { int []arr = { 1, 1, 1, 1, 2, 3, 4}; int більшість = findMajority(arr); Console.Write(' Елемент більшості: ' + більшість); } } // Цей код створено 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)) повернути кандидата; повернення -1; // Останній цикл for і крок оператора if можна // пропустити, якщо підтверджено, що елемент більшості // присутній в масиві, // у цьому випадку повертає кандидата } // Код драйвера var arr = [ 1, 1 , 1, 1, 2, 3, 4]; var most = findMajority(arr); document.write(' Елемент більшості: ' + більшість); // Цей код створено shivanisinghss2110.> |
java volatile ключове слово
>
>Вихід
The majority element is : 1>
Часова складність: O(n) (Для двох проходів по масиву)
Космічна складність: О(1)