Boyer-Mooreアルゴリズム

問題の定義
長さnの配列を指定します.

int[] nums

そのうちの1つの数は、n/2より多く、主要要素と呼ばれ、それを見つけた.
難題ではないように見えますが、面白いです.
これは投票問題で、私たちが投票採決時の採票過程をシミュレートすることができます.1つのhash tableまたはdictionaryを使用して、配列の数をkeyとし、それらが現れる回数はvalueです.本論文で議論したいのは,下のアルゴリズムである.
1.一般的な解法
1.1ソート
結論は簡単です.ソートが完了すると、主な要素は必ず下のn/2の位置にあります.次の2つの例を見るとわかります.

nums:    1,  1,  1,  2,  2
  i      0   1   2   3   4
n/2
=5/2
=2
nums[2]=1
         ，         

nums:    1,  1,  2,  2,  2
  i      0   1   2   3   4
n/2
=5/2
=2
nums[2]=2
         ，         

主要要素が最大でも最小でもない場合、主要要素はn/2を含む中間セグメントに集中する.Pythonは一言で終わりました.

def majorityElement(self, nums):
        return sorted(nums)[len(nums)/2]

解析:要素はint型であり,より小さな範囲を制限することなく,比較に基づくソートアルゴリズム,最速O(nlogn)である.
1.2ビット操作
ここでintを32ビット整数とする.これらの数をバイナリ形式でビット毎に観察し,主要元素の構築を試みた.32ビットの各ビットに対して、1が多数を占める場合、プライマリ要素の対応するビットは1であり、そうでない場合は0である.

nums:  1,  2,  3,  3,  3
Binary:
  1:   0b0000....0001
  2:   0b0000....0010
  3:   0b0000....0011
  3:   0b0000....0011
  3:   0b0000....0011

major: 0b0000....0011

Java実装:

public int majorityElement(int[] nums) {
      int res=0,major=nums.length/2;
      for (int i=31;i>=0;i--){
          int pos=0;
          for(int n:nums)
              pos+=(n>>i)&1;
          pos=pos>major? 1:0;
          res|=pos<

解析:時間的複雑度はO(n)であり,係数32を持ち,実際には動作が速い.
2.Boyer-Mooreアルゴリズム
Boyer‐Mooreアルゴリズムの論文を提出した.
基本思想:
比較的直感的な解釈:配列内に2つの異なる要素を見つけて削除し、配列内の要素が同じになるまで繰り返し、残りの要素が主要な要素になります.
思想は複雑ではないが、このアルゴリズムを空想するのも容易なことではない.また、配列を与えてくれて、直接要素を削除するのは時間がかかります.代わりに、カウント変数を用いて実現することができる.

def majorityElement(self, nums):
    count,major=0,0
    for n in nums:
        if count==0:
            major=n
        if major==n:
            count+=1
        else:
            count-=1
    return major

上のコードについて:

まず任意に候補要素を決定し、countは候補要素のカウントであり、候補要素とは異なる要素に遭遇した場合、両者の数は1つ相殺され、countは1減少する.countが0になると、候補要素を探し直します.

候補要素とは異なる要素に遭遇した場合、相殺される.候補要素と現在の要素については、A.のうちの1つが主要要素

である場合があります.
B.どちらも主要な要素ではない
状況Aに対して、相殺した後、主な要素はやはり主な要素である.ケースBに対しては,主な要素の地位が強固になったといえる.アルゴリズムは最終的に主要な要素を見つけることができます