配列の多数決要素を見つける
1. 概要
このチュートリアルでは、配列の多数決要素を見つける方法について説明します。最初に問題を簡単に紹介し、次にそれらの長所と短所を分析する3つのアルゴリズムを示します。 。
2. 序章
配列の過半数の要素は、入力の要素の半分以上で繰り返し発生する要素です。 数列がある場合、多数決要素は少なくともその数列に現れます。 もちろん、多数決条件を満たす要素が常に存在するとは限りません。 たとえば、次の7つの整数の配列があるとします。
この長さ7のシーケンスの大部分の要素（存在する場合）は、少なくとも1回出現する要素です。 ただし、上記のシーケンスで最も頻繁に使用される要素は、3回出現する整数1です。 したがって、常に多数決要素があるとは限らないことがわかります。
整数を整数に置き換えましょう：
ここでも、最も頻繁に表示される番号は1で、4回表示されます。 長さが7であるため、マジョリティ条件が成立し、整数がマジョリティ要素になります。
3. 素朴なアプローチ
多数決要素を見つけるための簡単なアプローチは、配列内の各要素の頻度を計算することです。これを実現するために、配列をループし、適切なデータ構造を使用して各要素の頻度を更新します。 次に、すべての要素とそれに対応する頻度を調べ、多数決条件に基づいて多数決要素が存在するかどうかを判断します。
データ構造として、各要素の値をキーとして、その頻度を値として格納する辞書を使用できます。 このアプローチの擬似コードを以下に示します。
前の例では、辞書は次のようになります。
そうすれば、整数1が多数決要素であることを簡単に確認できます。 このアルゴリズムは多数決要素を正しく計算しますが、その空間の複雑さはです。 過半数の要素があるかどうかを検出するには、すべての要素を辞書に保存する必要がある場合があります。
4. 改善されたアプローチ
スペースの複雑さに関するより良いアルゴリズムは、最初に入力シーケンスを並べ替えてから、中央値要素の頻度をチェックすることです。多数決要素がある場合は、中央値が唯一の可能な多数決要素です。ソートされたシーケンスの中央。 中央値が多数派要素であるかどうかを確認するために、その頻度を測定し、多数派条件が成立するかどうかを確認します。
この改善されたアプローチの擬似コードを上に示します。
たとえば、シーケンス例のソートされたバージョンは次のとおりです。
中央値は（4番目の要素）であり、実際に多数派の要素です。 このアプローチの時間と空間の複雑さは、使用される並べ替えアルゴリズムによって異なります。 使用する並べ替えアルゴリズムに関係なく、時間計算量は常に少なくともになります。
5. ボイヤームーアアルゴリズム
次に、線形時間と一定の空間の複雑さでシーケンスの大部分の要素を計算するボイヤームーアアルゴリズムに移りましょう。 これを実現するには、2つの変数が必要です。
- これは、現在可能な多数決要素を表します
- これは、ある要素の外観が過剰であるかどうかを示します
シーケンスがあるとしましょう：
まず、とを設定して変数を初期化します。 次に、シーケンスをループし、-番目の要素で次のことを確認します。
- の場合、とを設定します。
- かどうかを確認すると。 はいの場合は1増加し、そうでない場合は1減少します。
シーケンス全体をループした後、の最終値は候補の多数決要素です。 それが実際に多数決要素であるかどうかを確認するために、その頻度を計算し、多数決条件が成立するかどうかを確認します。
手順全体は、上記の擬似コードに要約されています。
最初のパスの後、可能な多数決要素は整数であることがわかります。 2回目のパスでその頻度を数えると、整数が多数決要素であることを確認します。
6. アルゴリズムの比較
上記の表では、各アルゴリズムの時間と空間の複雑さを要約しています。
ボイヤームーアアルゴリズムは、時間計算量と空間計算量の大部分の問題に最適なアルゴリズムであることがわかります。
7. 結論
この記事では、シーケンス内の多数決要素を計算する方法について説明しました。 最初に2つの簡単なアプローチを提示し、スペースの複雑さに関するそれらの欠点について説明しました。 次に、線形時間と一定の空間の複雑さで実行されるボイヤームーアアルゴリズムを紹介しました。
