配列内のn個の要素のリストを指定して、リスト内にn/3回以上出現するすべての要素を検索するアルゴリズムを設計します。アルゴリズムは線形時間で実行する必要があります（n> = 0）
比較を使用して線形時間を達成することが期待されます。ハッシュなし/過剰なスペース/そして標準の線形時間決定論的選択アルゴリズムを使用しませんか？問題は私が感じる自己ブロッキングですか？
1 に答える
1
ヒント：ボイヤーとムーアの線形時間投票アルゴリズムを見てください
手順：
- 0（n）時間の中央値アルゴリズムの中央値を使用して配列の中央値を検索します
- ピボット要素として中央値を使用するパーティション
-
a ）中央値と最初の要素と
b）中央値と最後の要素の間の各部分でムーアの投票アルゴリズムを使用します
- 中央値が必須要素であるかどうかを確認してください。
この問題を解決するためのより詳細なアルゴリズムについては、このドキュメントを参照してください。本当に、これは非常に役に立ちます。
その他の回答についても、この同様の投稿を参照してください。
于 2012-07-02T09:17:21.087 に答える