Boyer-Moore大多数投票アルゴリズムの2回目の要求の必要性

Question

私はBoyer-Mooreアルゴリズム（here）を勉強しています。私は簡単な質問がありました。その要素の頻度を見つける）。最初のパス自体はの要素が大部分のものであることを保証していませんか？私はいくつかの例を考えてと感じました。私の気持ちに対抗するためのいくつかの例を親切に教えていただけますか？ （必要な場合）

コードは以下の通りです：

int majorityElement(vector<int>& nums) { 
    int candidate=0, count=0; 

    for(auto value: nums) { 
     //update the candidate if the count == 0 
     if(count==0) 
      candidate=value; 

     //if the value == candidate then increment count 
     if(value==candidate) 
      count++; 
     else 
     //decrement count 
      count--; 
    } 

    //return candidate 
    return candidate; 
} 

編集：私が正しく理解していれば大多数の要素の周波数が実際に(vector size())/2よりも大きい場合、アルゴリズムにのみ適用されます。だから、2回目のパスは本当に必要ですか？コードを書くたびに、（入力ベクトルが空であるかどうかを確認するなどの）簡単な健全性チェックを行います。この場合、なぜアルゴリズムの一部として「健全性チェック」を使用するのでしょうか？それとも何かもっとあるの？

Answer 1

Boyer-Mooreアルゴリズムの次のような直感は、なぜ2つのパスが必要なのかを明らかにするかもしれないと思います。

アルゴリズムは以下の考え方に基づいています。あなたの配列の各要素が、番号の付いたカードを持っている部屋の人であるとします。部屋の各人は、他の人と出会うまで徘徊します。 2人の人が異なる番号を持っている場合は、それぞれが座っています。それ以外の場合は、他の人と出会うまで動き続けます。最終的には、いくつかの人が立つままになります。

真の多数決要素がある場合、人々がどのようにペアを張っても大多数の人が排除されているにもかかわらず、立っている最後の人々のグループには必ず多数の要素があります。しかし、過半数がない場合、依然として非過半数の要素を保持している人が最後に立っている可能性があります。たとえば、たぶん彼らは、他の誰もが座っていた間に、異なる価値を持つ誰かに出会ったことがなかったかもしれません。

2番目の理由は、これらの2つの場合を区別するためです。もしも過半数があれば、それは最終候補になります。もし存在しなければ、最終的な候補として何かが残っている可能性があり、あなたはそのケースを支配する必要があります。

Answer 2

あなたは何の過半数の要素が混乱していると思いますか？候補のみ資格その周波数がより総リストの半分以上である場合、すなわち

if frequency(majority_element) > total_size_of_list/2: return True 

最初のパスは、過半数投票のための可能な候補を取得します。 2番目のパスは、それが本当に多数決要素かどうかを確認します。

例えば： - 多数の要素については、次のリストで

[1, 2, 2, 3, 3, 4, 4, 5, 5, 5] 

可能な候補は5 であるが、リスト内の5の周波数は3のみどの少ないリストサイズの半分以下であるので、それはあります過半数の要素ではないので、テストは失敗しますが、2回目のパスを行わなければ、それを知ることさえできません。

私はそれが助けてくれることを願っています！