algorithm - n要素配列で要素がn/4回出現するかどうかを求めます

Question

こんな質問をされました。多数要素法を使用しようとしましたが、うまくいきませんでした。ヒントを教えてください。

Answer 1

1. 時間の中央値を見つけますO(n)。
2. 3 分割を使用して、その中央値に基づいて配列を分割します。
3. 中央値自体が必要な要素である場合は実行され
   ます。それ以外
   の場合は、パーティションの両方 (中央値の左右) で多数要素アルゴリズムが適用されます。（あなたの場合、n/2の配列でn/4回以上現れる要素を見つけてください）。どちらもO(n)時間内に実行されます。

合計時間は です3*O(n)=O(n)。
お役に立てれば ：）