Majority Element I
https://leetcode.com/problems/majority-element/
首先题中数组中某一元素是majority(超过一半都是这个元素)，请找出这个元素。
最naive的应该是 scan and count， 需要辅助空间 时间空间复杂度都是 $O(n)$
也可以排序或者quick select后，直接取中位数，时间复杂度是排序 $O(n\log n)$.
这里探讨几个经典的做法
Majority Vote
用一个计数器，迭代这个数组，当计数器为0的时候，将当前元素记为结果，然后每遇到一个相同元素，则计数器加一，反之则减一。 原理是假设不同元素可以两两相消，那么最后剩下的一定是majority element. 这种情况是1pass，如果你被告知这里一定有这样一个majority vote。否则， 你需要再加上一轮verify，其实是一个2pass， 即 2N次比较。 那么如果是这样，允许不存在majority，最好的算法是？ 这里简要的介绍了这么一个算法，来自一篇很老的paper。其中证明了optimal的比较次数是 $3n/2-2$. 这个算法需要额外的空间。
1class Solution(object):
2 def majorityElement(self, nums):
3 """
4 :type nums: List[int]
5 :rtype: int
6 """
7 res = 0
8 counter = 0
9 for x in nums:
10 if counter == 0:
11 counter +=1
12 res = x
13 else:
14 if res == x:
15 counter +=1
16 else:
17 counter -=1
18 return res