algorithm - 配列にn/3回以上出現する数

Question

私はこの問題を読み ました配列内の最も一般的なエントリを見つけます

そして、ジョン・スキートからの答えはただ気が遠くなることです.. :)

今、私はこの問題を解決しようとしています。配列内でn/3回以上発生する要素を見つけます。

n / 3回以上発生する2つの要素があり、カウントの誤警報が発生する可能性があるため、同じ方法を適用できないと確信しています。ジョン・スキートの答えを微調整する方法はありますか。このために働く..？

または、線形時間で実行されるソリューションはありますか？

Answer 1

Jan Dvorak の答えがおそらく最良です。

• 2 つの空の候補スロットと 0 に設定された 2 つのカウンターから始めます。
• 各項目について:
  • いずれかの候補と等しい場合は、対応するカウントを増やします
  • 空のスロット (つまり、カウント 0 のスロット) がある場合は、そのスロットに入れ、カウントを 1 に設定します。
  • それ以外の場合は、両方のカウンターを 1 減らします

最後に、配列に対して 2 回目のパスを行い、候補が実際に必要な数を持っているかどうかを確認します。これはリンク先の質問では許可されていませんが、この変更されたバージョンで回避する方法がわかりません。n/3 回以上発生する値がある場合、それはスロットになりますが、それがどれであるかはわかりません。

この修正されたバージョンの質問で、以上の要素を持つ2 つの値 (一般に、以上の値) が存在することが保証されている場合、2 番目のパスは必要ありません。しかし、元の質問が過半数を保証しており、そのような要素が 1 つ保証されているか、または が保証されているかを一般化する必要があるかどうかを知る方法はありません。保証が強いほど、問題はより簡単になります。n/3k-1n/kk=2k-1

Answer 2

選択アルゴリズムを使用して、n/3の場所と2n/3の番号を見つけることができます。

n1=Selection(array[],n/3);
n2=Selection(array[],n2/3);
coun1=0;
coun2=0;

for(i=0;i<n;i++)
{
    if(array[i]==n1)
      count1++;
    if(array[i]==n2)
      count2++;
}
if(count1>n)
   print(n1);
else if(count2>n)
   print(n2);
else
   print("no found!");