以上のn/8倍

Question

質問がある表示され、アレイ内の数字がある場合に検索：

は、n個の数字の配列に存在する場合はO（n）時間で見つけるアルゴリズムを説明し、aはn/8回以上出現する数。我々は場所で番号の選択やる

：

は今、私はある答えを持ってN/9,2 * N/9,3 * N/9、...、8 * N/9であり、8人の候補のうちの1人が少なくともn/8回出現するかどうかをチェックする。

しかし、なぜこのアルゴリズムが動作するのかわかりません。

たとえば、次の配列を考えます。 [3,3,1,3,2,3,4,3,5,3,6,3,7,3,8,3,9,3] 。

ここでn = 18であり、このアルゴリズムでは候補が1,2,4,5,6,7,8,9であり、これらの数字が少なくともn/8回現れるかどうかチェックするとき答えは「いいえ」ですが、実際には3の答えは「はい」になります。

は、だから私は...正しいこのアルゴリズムである理由を理解していない

Answer 1

ここで重要な洞察を選択し、大文字場合は特に、特別な意味を持っているということです。それは、k番目で最大のエントリを見つける問題を参照並べ替えられていない配列恐らく多少驚くほど先験的であるが、これは例えばQuickSelectアルゴリズムと組み合わされたメジアン・オブ・ピボット戦略を使用して、線形時間で行うことができる。したがって、n/9、2n/9、...エントリ（コスト：9 *線形 - 線形）を選択して大文字 - 小文字を選択すると、n/8回発生するエントリを見つけることができます。次に、配列を繰り返して、これらの候補のそれぞれの出現回数を数えます。そして、完了したらすぐに実行してください。