問(wèn)題定義

給定一個(gè)長(zhǎng)度為 n的數(shù)組:
int[] nums
其中有一個(gè)數(shù)，它出現(xiàn)的次數(shù)大于n/2，稱(chēng)為主要元素，找到它。
看起來(lái)不算是個(gè)難題，但好玩。
這是一個(gè)投票問(wèn)題，可以模擬我們?cè)谕镀北頉Q時(shí)的計(jì)票過(guò)程。用一個(gè)hash table或者dictionary，數(shù)組中的數(shù)作為key，它們出現(xiàn)的次數(shù)為value。這樣的算法，時(shí)間和空間復(fù)雜度都是O(n)。
本文想討論的是下邊這些算法。

1.常見(jiàn)解法

1.1 排序

結(jié)論很簡(jiǎn)單：排序完之后，主要元素必然在下標(biāo)n/2的位置。
看下面兩個(gè)例子就很清楚了:

nums:    1,  1,  1,  2,  2
  i      0   1   2   3   4
n/2
=5/2
=2
nums[2]=1
主要元素是最小的數(shù)，排序后集中在最左邊

nums:    1,  1,  2,  2,  2
  i      0   1   2   3   4
n/2
=5/2
=2
nums[2]=2
主要元素是最大的數(shù)，排序后集中在最右邊

如果主要元素既不是最大的也不是最小的，那主要元素集中在中間一段，包括n/2。
Python一句搞定：

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

分析:
元素是int型，沒(méi)有限制更小的范圍，基于比較的排序算法，最快O(nlogn)。

1.2 位操作

這里設(shè)int為32位整數(shù)。我們對(duì)這些數(shù)以二進(jìn)制的形式，逐位觀察，嘗試構(gòu)造出主要元素來(lái)。對(duì)32位中的每一位，如果1占多數(shù)，則主要元素的對(duì)應(yīng)位為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實(shí)現(xiàn)：

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<<i;
        }
      return res;
    }

分析：
時(shí)間復(fù)雜度為O(n)，帶個(gè)系數(shù)32，實(shí)際工作起來(lái)還是很快的。

2. Boyer-Moore算法

提出Boyer-Moore算法的論文。
基本思想：
比較直觀的解釋?zhuān)涸跀?shù)組中找到兩個(gè)不相同的元素并刪除它們，不斷重復(fù)此過(guò)程，直到數(shù)組中元素都相同，那么剩下的元素就是主要元素。
思想并不復(fù)雜，但是要憑空想出這個(gè)算法來(lái)也不是件容易的事。另外，給我們的是數(shù)組，直接在里面刪除元素是很費(fèi)時(shí)的。取而代之，可以利用一個(gè)計(jì)數(shù)變量來(lái)實(shí)現(xiàn)。

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

對(duì)于上面的代碼：
先隨意確定一個(gè)候選元素，count是候選元素的計(jì)數(shù)，當(dāng)遇到一個(gè)跟候選元素不同的元素時(shí)，兩者數(shù)量上抵消一個(gè)，count減1。一旦count變成0，就重新找一個(gè)候選元素。
當(dāng)遇到一個(gè)與候選元素不同的元素時(shí)，就要抵消。對(duì)于候選元素和當(dāng)前元素，可能存在兩種情況：1）兩者中有一個(gè)正好是主要元素；2）兩者都不是主要元素。
對(duì)于情況1)，抵消過(guò)后，主要元素還是主要元素；對(duì)于情況2），可以說(shuō)主要的元素的地位得到了鞏固。所以算法最終能找到主要元素。
One More Thing
上面的題目指出，滿(mǎn)足條件的元素一定存在，那就可以直接返回我們找到的元素了。但事實(shí)上有時(shí)候這樣的元素不一定存在，那么當(dāng)我們找到這樣一個(gè)元素時(shí)，還要進(jìn)一步驗(yàn)證一下它是否滿(mǎn)足條件。很簡(jiǎn)單，再遍歷一遍，統(tǒng)計(jì)它的出現(xiàn)次數(shù)。

3. Generalization

如果題目是這樣的：
找出 int[] nums中出現(xiàn)次數(shù)大于（不等于）n/3的元素，咋整。
解：首先可以明確的一點(diǎn)是，這樣的元素可能有0個(gè)、1個(gè)、或者2個(gè)，再?zèng)]有別的情況了。
然后，我們的Boyer-Moore算法思路，在這里依然可用，但需要些改動(dòng)：
1)滿(mǎn)足條件的元素最多有兩個(gè)，那么需要兩組變量。上面的count, major變成了count1, major1; count2, major2。
2)選出的兩個(gè)元素，需要驗(yàn)證它們的出現(xiàn)次數(shù)是否真的滿(mǎn)足條件。

def majorityElement(self, nums):
    candi1,candi2, count1,count2=0, 1, 0, 0
    for n in nums:
        if count1==0:
            candi1, count1=n, 0
        elif count2==0:
            candi2, count2=n, 0
        if n==candi1:
            count1+=1
        elif n==candi2:
            count2+=1
        else:
            count1-=1
            count2-=1
    #驗(yàn)證條件
    res=[n for n in set([candi1,candi2]) if nums.count(n)>len(nums)/3]
    return res