問題定義

給定一個長度為 n的數(shù)組:
int[] nums
其中有一個數(shù)，它出現(xiàn)的次數(shù)大于n/2，稱為主要元素，找到它。
看起來不算是個難題，但好玩。
這是一個投票問題，可以模擬我們在投票表決時的計票過程。用一個hash table或者dictionary，數(shù)組中的數(shù)作為key，它們出現(xiàn)的次數(shù)為value。這樣的算法，時間和空間復(fù)雜度都是O(n)。
本文想討論的是下邊這些算法。

1.常見解法

1.1 排序

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

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型，沒有限制更小的范圍，基于比較的排序算法，最快O(nlogn)。

1.2 位操作

這里設(shè)int為32位整數(shù)。我們對這些數(shù)以二進制的形式，逐位觀察，嘗試構(gòu)造出主要元素來。對32位中的每一位，如果1占多數(shù)，則主要元素的對應(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實現(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;
    }

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

2. Boyer-Moore算法

提出Boyer-Moore算法的論文。
基本思想：
比較直觀的解釋：在數(shù)組中找到兩個不相同的元素并刪除它們，不斷重復(fù)此過程，直到數(shù)組中元素都相同，那么剩下的元素就是主要元素。
思想并不復(fù)雜，但是要憑空想出這個算法來也不是件容易的事。另外，給我們的是數(shù)組，直接在里面刪除元素是很費時的。取而代之，可以利用一個計數(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

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

3. Generalization

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

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
    #驗證條件
    res=[n for n in set([candi1,candi2]) if nums.count(n)>len(nums)/3]
    return res