2

n (必ずしも異なる) 整数の配列 A[1...n] を指定すると、A で n/4 回の上限を超えてアイテムが発生するかどうかを判断するアルゴリズムを見つけるという問題があります。

可能な限り最良の最悪のケースの時間はO(n)のようです。私は多数要素アルゴリズムを認識しており、これがこの状況に適用されるかどうか疑問に思っています。この問題にアプローチするための提案があれば教えてください。

4

2 に答える 2

5

これはアルゴリズムのアイデアにすぎませんが、機能させることは可能だと思います。

主なトリックは次のとおりです。4つの要素を見て、それらがすべて異なっている場合は、4つすべてを捨てることができます. (スローされた要素のいずれかが古い配列で 1/4 を超える頻度を持っていた場合、それは新しい配列に含まれます。そうでない場合は、どれもありません)。

したがって、配列を調べて、4 つのタプルを破棄し、残りを再配置します。たとえば、AABC の次に DDEF がある場合は、AADDBCEF に並べ替えて BCEF を捨てます。詳細はお任せします。難しいことではありません。最終的には、同じ要素のペアが残るはずです。次に、奇数番号の要素を捨てて繰り返します。

各実行後、捨てることができないペアのない 1、2、または 3 つの要素が残る場合があります。残りの山に 3 つ以上の要素がないように、2 つの実行の残りを組み合わせることができます。たとえば、実行 1 の後に A、B、C があり、実行 2 の後に A、D、E がある場合、A だけを残します。残りの各要素のカウントを保持して、どの要素を破棄できるかを追跡します (最後の残りの要素を常に保持できる場合がありますが、私は確認していません)。

最後は残り物だけになります。それぞれを元の配列と照合します。

于 2013-11-05T08:38:10.003 に答える
-2

この要素には、配列の中央値、配列の n/2 最小要素の中央値、または配列の n/2 最大要素の中央値の 3 つの可能性があります。

いずれの場合も、最初に配列の中央値を見つけます。その後、少なくとも n/4 要素で発生するかどうかを確認し、そうでない場合は、配列をほぼ同じサイズの 2 つの部分に分割します (サイズの違いは最大でも 1 要素です)。

  • 中央値より小さい
  • 中央値以上

次に、これら 2 つの部分配列のそれぞれの中央値を見つけ、それぞれの出現回数を確認します。これはすべて O(n) です。また、この方法で、少なくとも n/4 回出現するすべての要素を見つけることができます。

ところで、この手法を拡張して、O(n) 回出現する要素 (たとえば、n/10000) を見つけることができます。これは、O(n) で再び機能します。

于 2013-11-05T09:41:21.553 に答える