問(wèn)題定義
給定一個(gè)長(zhǎng)度為 n的數(shù)組:
int[] nums
其中有一個(gè)數(shù)棚亩，它出現(xiàn)的次數(shù)大于n/2，稱為主要元素虏杰，找到它讥蟆。
看起來(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算法的論文奴紧。
基本思想：
比較直觀的解釋：在數(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
上面的題目指出，滿足條件的元素一定存在渤闷，那就可以直接返回我們找到的元素了疾瓮。但事實(shí)上有時(shí)候這樣的元素不一定存在，那么當(dāng)我們找到這樣一個(gè)元素時(shí)飒箭，還要進(jìn)一步驗(yà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)滿足條件的元素最多有兩個(gè)劈伴，那么需要兩組變量。上面的count, major變成了count1, major1; count2, major2握爷。
2)選出的兩個(gè)元素跛璧，需要驗(yàn)證它們的出現(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
#驗(yàn)證條件
res=[n for n in set([candi1,candi2]) if nums.count(n)>len(nums)/3]
return res
