algorithm - 最も頻度の高い要素を見つける

Question

ボールにはいくつかの色があります。1つの特定の色について、この色（> n / 2）のボールの半分以上があります。O（n）の実行時間だけでこの色を見つけるにはどうすればよいですか？

Answer 1

ボイヤームーア多数決アルゴリズムを使用できます

Answer 2

各ボールの色を見つけて、それを集計します。最も頻繁に検索したいだけの場合、これは並べ替えではないようです。各色のボールの数を数えるだけです。ハッシュテーブルを使用できます。キーは色であり、スポットを繰り返すだけです。また、色を追跡します。

編集：これをもう一度読んだ後、私はそれが質問に答えていないことに気づきました。

A）比較はn未満であり、最悪の場合はO（n）になるため、使用可能なすべての色を反復処理することで、最後に追跡を行うことができます（色のリストを作成していると仮定します）。

B）ボールのカウントを集計している間、最大のカウントを追跡します。それが打ち負かされるときはいつでも、それを最も多いカウントの現在の色に置き換えてください。あなたはおそらく最大の数と一緒に色を追跡したいと思うでしょう。このようにして、実行ごとの比較でそれを行います。これもO（n）になりますが、より多くの比較が行われます。