n/kより大きい出現回数の重複要素を検索する---非多重セットアルゴリズム

本文は1篇の英語の論文に対する総括です:Finding Repeated Elements.原文を見たいなら、Googleの方へどうぞ.
この問題の単純な形式は,「n/2より大きい出現回数の繰返し要素を検索する」ことである.私たちはまず簡単な問題から始めて、それから拡張します.
1.出現回数がn/2より大きい重複要素の検索
「プログラミングの美しさ」には同じ問題「投稿水王を探す」があり、具体的な構想は毎回2つの異なる要素を削除し、最後に残ったのは要求された要素である.この結論の証明は以下の通りである.
n,mは正の整数であり,nは配列の長さを表し,mはn/2より出現回数が大きい要素の個数,すなわちm>n/2であることが知られている.
証明が必要な結論は2つあります.
(1)n/2より出現回数が大きい要素をvで表す.2つの異なる要素が削除され、そのうちの1つがvである場合、mは1を減少させ、nは2を減少させる.
証明を求めます:m-1>(n-2)/2
証明:m-1>n/2-1=(n-2)/2
(2)2つの異なる要素を削除し、そのうちの1つがvでない場合、nを2だけ小さくする必要がある.
証明を求めます:m>(n-2)/2.この結論は明らかだ.
コードは次のとおりです.

int find(int array[],　int n)
{
    int candidate;
    int count=0;
    for(int i=0;i<n;++i)
    {
        if(count==0)
        {
             candidate=array[i];count=1;
        }
        else
        {
             if(candidate==array[i])
                   ++count;
              else 
                   --count;   
        }       
    }  
    return candidate;
}

「プログラミングの美」の後の練習問題は「出現回数がn/4より大きい要素を検索する」で、構想は毎回異なる4つの要素を削除し、最後に残りの3つが候補要素であるが、この3つの要素が条件を満たしているかどうかを検証しなければならない.詳しく説明しません.実は『プログラミングの美しさ』の中で言う方法は本論文の後で言及した“多重集”アルゴリズムです.
まず論文の中のあのような非多重セットアルゴリズムを話します.使用する変数は次のとおりです.
b[]:要素が存在する配列
i:配列インデックス
v:検索する値を保存します.つまり、n個の要素を巡回した後、vの出現回数はn/2より大きいです.
c:vの出現回数の上限の2倍、すなわちvの出現回数はc/2以下である.
初期化、i=0、v=null、c=0.
b[]配列を巡回し、b[i]に巡回するたびに、次の2つの状況が発生します.
(1)b[i]=v
b[i]=vのため、vの出現回数はまた1増加し、cの意味を維持するために、すなわちc/2も1増加させるために、cは2増加する.
(2)c=i
このステップでは、b[0...i-1]の任意の要素の出現回数がi/2を超えないことを証明するには、vを更新する必要があります.
cが2ずつ増加し、iが1ずつ増加する前の遍歴cとiの関係を先に打ち出し、今回の遍歴でc=iを譲るためには、前の遍歴ではiが1増加したに違いないが、cは増加しなかった.したがって、前回のループの前にcとiの関係はc=i+1であり、前回のループの終了時にcはiと等しい.
前回の遍歴時の状況を再考察する:mにvの出現回数を表すようにすると、前回の遍歴前の場合はm>i/2であり、m<=c/2=(i+1)/2であり、式:i/2今回の遍歴が直面する状況はc=iであり、配列b[0...i-1]ではvの出現回数がc/2であり、vを除く他の要素の出現回数がi-m=i-c/2=i-i/2=i-i/2=i/2であることは、b[0...i-1]のいずれの要素の出現回数もi/2を超えていないことを示しており、vを更新する必要がある.最も可能性のある要素はb[i]であり、実際には最終的にb[i]ではない可能性がある.
コード:

   const int N=9;
   int b[N]={2,3,3,2,2,2,1,1,2};
   int v=-1, c=0, i=0;
   while(i!=N)
   {
       if(v==b[i])
       {
           c+=2;            
       }
       else if(c==i)
       {
          v=b[i];
          c+=2;        
       }
       ++i;    
   }
   cout<<v<<endl;

条件を満たすvが存在しない場合、vの値は最後の数である.
2.出現回数がn/kより大きい要素の検索
2<=k<=nと配列b[0...n−1]を与えると、n/kより大きい出現回数を持つ要素を検索する.
問題1.で、実際には配列を2つの集合に分け、1つの集合は1つの要素v(または空)のみを含み、もう1つの集合はn/2以下の出現回数の要素を含む.同様に、私たちはそれを拡張して、依然として配列を2つの集合に分けて、1つの集合はn/kより大きい可能性のある要素を含んで、1つの集合はn/kより小さい出現回数の要素を含んでいます.
関連変数は次のように宣言されます.
v:出現回数がn/kより大きい可能性のある要素
c:vの出現回数はc/2を超えない
集合t:(v,c)のような形の値対を含む.
s:出現回数がn/k以下の要素について、その出現回数の上限をs/kとする.
アルゴリズムは2つの段階を含む:まず、集合tを選択する;次に、t内の要素が条件を満たしているかどうかを検証します.ここでは第1段階のみを説明する.第2段階の複雑さはO(n*log(t))である.

i=0,s=0,t={};
for(;i<n;++i)
{
     t   v=b[i]   (v_j,c_j),j    ;           ,  j=0;
    if(j==0 && s+k<=i+1)
    {
        s=s+k;
    } 
    else if(j==0 && s+k>i+1)
    {
          (b[i],s+k)    t ;     
    }
    else // j!=0
    {
         c_j=c_j+k; 
    } 
    i=i+1;
      t     c=i   。       ，  s=i;          
}

3つのif文をそれぞれ説明します.
(1)j=0かつs+k<=i+1
v=b[i]の要素が見つからない場合は、現在の要素b[i]がセットtに入れるべきか否かを判断する.b[i]が集合tに入れるべきでない場合、今回の反復後にb[i]が現れる回数上限(s+k)/k<=(i+1)k、すなわち条件:s+k<=i+1であることを説明する.
(2)j=0かつs+k>i+1
b[i]が集合tに入れるべきである場合、今回の反復後にb[i]が現れる回数の上限(s+k)/k>(i+1)k、すなわち条件:s+k>i+1であることを説明する.(3) j!=0
v=b[i]の要素が見つかった場合は、c_を更新します.jの値.だってv_jの出現回数が1増加するのでc_j/kも1増加、すなわちc_j = c_j + k.
b[i]の処理が完了すると、集合tの一部の要素のc値が期限切れになる可能性がある.期限切れの条件は何ですか?c/k>=(vの出現回数)>i/k、すなわちc/k>i/kの条件があるため、c>iに簡略化される.iは増加するが、cは増加しない可能性があるので、c=iの場合、cは期限切れになる.このとき,このような要素をtから削除する.なぜsの値を更新するのですか?まだ分からない.
アルゴリズムの第1段階の複雑さもO(n*log(t))である.tには最大何個の要素がありますか?論文では|t|の最大値はk*log(k)である.したがってアルゴリズム全体の複雑さはO(n*k*log(k))である.