169 majority element
169. Majority Element
题目: https://leetcode.com/problems/majority-element/
难度: Easy
思路：
其实这个我有点有想到过
给定一个长度为 n的数组,其中有一个数，它出现的次数大于⎣n/2⎦，称为主要元素，找到它.
这个很像之前做过的一道CLRS的题目，想法可以用divide & conquer.
- 如果数组长度 <= 2,那么return第一个即解决问题
- 如果长度 > 2，那么可以两两配对，对于配对一样的结果，删去
- 如果最后余一个，这一个留下
- shuffle之后再尝试两两配对，直到最后结果不再改变
这样肯定是能解决问题的，因为为了满足次数大于⎣n/2⎦这个条件。
1 2 1 2 1 2 1 2
2 3 2 3 2 3 2 3
2 4 2 2 2 2 3
2 4 2 3 3
3 2
2 2
2 2
思路容易implement非常难啊.
这个问题有一个很出名的算法
Boyer-Moore众数(majority number) 问题
在数组中找到两个不相同的元素并删除它们，不断重复此过程，直到数组中元素都相同，那么剩下的元素就是主要元素。
这个算法的妙处在于不直接删除数组中的元素，而是利用一个计数变量.
伪码
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
