Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
思路：
Find k different element, and “remove” them as a group, the remaining element must be the element that appears more than ⌊n/k⌋ times. (Detailed explanation is given in comment)
In this problem, k equals to 2.
Thus we “remove” each pair of 2 different elements, and the remaining element that do not have its counterpart is the desired element.
时间复杂度O(n)空间复杂度O(1)的算法呢? 实际上，早在91年就有人专门就这个问题发表了论文，介绍了一种线性时间的算法: Majority Vote Algorithm。通过名字就可以看出，这个算法是专门用来解决这个问题的。而由于作者是J Moore (目前是Utexas的计算机系主任)，这个算法有时候也会被称为Moore’s Voting Algorithm (当然这个Moore并不是提出Moore’s Law的那个Gordon Moore)。
算法的基本思想非常简洁: 每次都找出一对不同的元素，从数组中删掉，直到数组为空或只有一种元素。 不难证明，如果存在元素e出现频率超过半数，那么数组中最后剩下的就只有e。当然，最后剩下的元素也可能并没有出现半数以上。比如说数组是[1, 2, 3]，最后剩下的3显然只出现了1次，并不到半数。排除这种false positive情况的方法也很简单，只要保存下原始数组，最后扫描一遍验证一下就可以了。
现在来分析一下复杂度。删除元素可以在常数时间内完成，但找不同元素似乎有点麻烦。实际上，我们可以换个角度来想，用一个小trick来重新实现下该算法。
在算法执行过程中，我们使用常量空间实时记录一个候选元素c以及其出现次数f(c)，c即为当前阶段出现次数超过半数的元素。在遍历开始之前，该元素c为空，f(c)=0。然后在遍历数组A时，
如果f(c)为0，表示当前并没有候选元素，也就是说之前的遍历过程中并没有找到超过半数的元素。那么，如果超过半数的元素c存在，那么c在剩下的子数组中，出现次数也一定超过半数。因此我们可以将原始问题转化为它的子问题。此时c赋值为当前元素, 同时f(c)=1。
如果当前元素A[i] == c, 那么f(c) += 1。(没有找到不同元素，只需要把相同元素累计起来)
如果当前元素A[i] != c，那么f(c) -= 1 (相当于删除1个c)，不对A[i]做任何处理(相当于删除A[i])
如果遍历结束之后，f(c)不为0，那么再次遍历一遍数组，记录c真正出现的频率，从而验证c是否真的出现了超过半数。上述算法的时间复杂度为O(n)，而由于并不需要真的删除数组元素，我们也并不需要额外的空间来保存原始数组，空间复杂度为O(1)。实际上，在Moore大牛的主页上有针对这个算法的一个演示，感兴趣的同学可以直接移步观看。
这个问题看上去已经完美的解决了。
二、更一般的情况呢？
那么，如果我们想找的并不是超过半数的元素，而是出现频率超过一定频率的元素都要找出来，是否也存在一个类似的线性时间的算法呢?答案是肯定的。实际上，这一类从特定的数据集中找出出现频率超过某个阈值的元素的问题，有一个形象的名字叫做Iceberg query，或者叫做host list分析。而Richard Karp 老爷子当年就专门写了一篇论文来讨论这种一般性问题的解决方案，而通过下文的介绍，大家也可以发现，Karp的方案应该也是受到了Moore的算法的启发。
首先还是看一下问题的形式化定义吧:
对于一个序列 以及一个在(0,1)之间的实数。假定表示元素的出现频率，我们需要找到所有满足的元素。
原帖连接：
https://leetcode.com/discuss/19151/solution-computation-space-problem-can-extended-situation
http://m.blog.csdn.net/blog/wenyusuran/40780253
解决方案：
class Solution {
public:
int majorityElement(vector<int>& nums)
{
int size = nums.size();
int vote = 0;
int count = 0;
for(int i = 0;i < size;i++)
{
if(count == 0)
{
vote = nums[i];
count = 1;
}
else
{
if(vote == nums[i])
count++;
else
count--;
}
}
return vote;
}
};STL解决方案：
int majorityElement(vector<int> &num)
{
map<int, int>count;
for (vector<int>::iterator i = num.begin(); i != num.end();i++)
{
if ( (++count[*i]) > num.size() / 2)
return *i;
}
}
c语言：
int majorityElement(int num[], int n)
{
int cnt = 0, res;
for (int i = 0; i < n; ++i)
{
if (cnt == 0) res = num[i];
if (res == num[i]) ++cnt;
else --cnt;
}
return res;
}
python解决方案：
class Solution:
# @param {integer[]} nums
# @return {integer}
def majorityElement(self, nums):
count = {}
for i in nums:
if i not in count:
count[i] = 0
count[i] += 1
if count[i] > len(nums)/2:
return i