の ボイヤー・ムーア投票 アルゴリズムは、N/2 回以上出現する指定された要素の中から多数派の要素を見つけるために使用される、一般的な最適アルゴリズムの 1 つです。これは、指定された要素に対して 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 未満であることがわかっているためです。候補要素とは異なる要素がいくつか見つかったため、投票を減らし続けます。投票が 0 になるということは、実際には、さまざまな要素に同じ数の投票があることを意味しますが、その要素が多数派要素である場合には当てはまりません。したがって、候補要素が過半数になることはできないため、現在の要素を候補として選択し、すべての要素が終了するまで同じ操作を続けます。最終候補は多数派要素になります。 2 番目の走査を使用して、そのカウントが N/2 より大きいかどうかを確認します。それが本当であれば、それが多数派の要素であると考えられます。
アルゴリズムを実装する手順:
ステップ1 - 過半数を獲得した候補者を見つける –
- たとえば変数を初期化する i 、投票数 = 0、候補者 =-1
- for ループを使用して配列を走査する
- もし 投票 = 0、 を選択してください 候補者 = arr[i] 、 作る 投票=1 。
- それ以外の場合、現在の要素が候補の増分投票と同じである場合
- それ以外の場合は票を減らします。
ステップ2 - 候補者が N/2 票を超えているかどうかを確認します –
- 変数 count =0 を初期化し、候補と同じであれば count をインクリメントします。
- カウントが>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 Majority = findMajority(arr, n); コート<< ' 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 Majority = findMajority(arr); System.out.println(' 多数決要素は : ' + 多数決); } } // このコードは Arnav Sharma によって提供されています>> |
>
>
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>ん>> 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#
Javaローカルデート
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 Majority = 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 Majority = findMajority(arr); document.write(' 多数決要素は : ' + 多数決); // このコードは shivanisinghss2110 によって提供されました。>> |
>
>
Linuxのexportコマンドとは何ですか出力
The majority element is : 1>
時間計算量: O(n) (配列上の 2 つのパスの場合)
空間の複雑さ: ○(1)