그만큼 보이어-무어 투표 알고리즘은 N/2 이상 발생하는 주어진 요소 중에서 다수의 요소를 찾는 데 사용되는 인기 있는 최적 알고리즘 중 하나입니다. 이것은 O(N) 시간 복잡도와 O(1) 공간 복잡도에서 작동하는 주어진 요소에 대해 2번의 순회를 수행하는 주요 요소를 찾는 데 완벽하게 작동합니다.
예를 들어 작동 뒤에 숨은 알고리즘과 직관을 살펴보겠습니다.
자바 수면
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보다 작다는 것을 알고 있기 때문입니다. 후보 요소와 다른 요소를 발견했기 때문에 투표 수를 계속 줄입니다. 투표수가 0이 되면 이는 실제로 서로 다른 요소에 대해 동일한 수의 투표가 있음을 의미하며, 이는 요소가 다수 요소가 되는 경우가 되어서는 안 됩니다. 따라서 후보 요소는 다수가 될 수 없으므로 현재 요소를 후보로 선택하고 모든 요소가 완료될 때까지 동일하게 계속합니다. 최종 후보는 우리의 주요 요소가 될 것입니다. 두 번째 순회를 사용하여 해당 개수가 N/2보다 큰지 확인합니다. 그것이 사실이라면 우리는 그것을 다수의 요소로 간주합니다.
알고리즘을 구현하는 단계:
1 단계 - 다수를 차지하는 후보자 찾기 -
- 변수 초기화 i, 투표수 = 0, 후보 =-1
- for 루프를 사용하여 배열을 탐색합니다.
- 만약에 투표 = 0, 선택하다 후보 = arr[i] , 만들다 투표수=1 .
- 그렇지 않으면 현재 요소가 후보 증분 투표와 동일한 경우
- 그렇지 않으면 투표 수가 감소합니다.
2 단계 - 후보자가 N/2 표 이상을 얻었는지 확인하십시오 –
- 변수 개수를 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>n / 2) 후보자를 반환합니다. -1을 반환합니다. } int main() { int arr[] = { 1, 1, 1, 1, 2, 3, 4 }; int n = sizeof(arr) / sizeof(arr[0]); int major = findMajority(arr, n); 시합<< ' The majority element is : ' << majority; return 0; }> |
>
>
자바
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[ ] 인수) { int arr[] = { 1, 1, 1, 1, 2, 3, 4 }; int major = findMajority(arr); System.out.println(' 다수 요소는 : ' + 다수); } } // 이 코드는 Arnav Sharma가 제공한 것입니다.> |
>
>
파이썬3
# 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>엔>/>/> 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> |
>
>
씨#
그들은 가수들이다
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 major = findMajority(arr); Console.Write(' 다수 요소는 : ' + 다수); } } // 이 코드는 shivanisinghss2110이 제공한 것입니다.> |
>
>
자바스크립트
자바 현지 날짜
> // 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 majority = findMajority(arr); document.write(' 다수 요소는 : ' + 다수); // 이 코드는 shivanisinghss2110이 제공한 것입니다.> |
>
>산출
The majority element is : 1>
시간 복잡도: O(n) (배열을 두 번 통과하는 경우)
공간 복잡도: 오(1)