概述：

前几天校内春季赛的题，可惜因为有事而没能去参加。看了眼题目发现有一道题挺有意思的。

给定N个int值（N<=1e6） 求出现的次数大于N/2的数字。

乍看之下十分简单，然后内存容量2MB..

思考：

乍看之下只需要扫描一遍数组然后利用Map或是其他方法记录下所输入的值即可，但是2MB内存意味着我们并不能这么做(:зゝ∠) 所以我们需要一种线性时间内空间需求极小的算法。即摩尔投票法

引子：

思考这么一个问题，对于任意一个数组N，假设我们最终所求的值为val,那么val在整个数组N中的出现次数必然cnt(N)>N/2.假设我们现在扫描了前X个数，val值的出现次数为a次，那么在数组N的后半段N-X中，val的值还存在着cnt(val)-a次，显然cnt(val)-a的最小值为:
N/2+1-a.

那么对于数组的前半段X而言，val的出现值为a,对于数组的后半段N-X而言，val的出现值为cnt(val)/2+1-a，那么对于X或N-X而言，如果aN/2，反之亦然。

算法引出：

那么可以看出，对于X或者N-X，我们不知道究竟是a更大，还是cnt(val)-a+1更大，但是对于这两段区间，若若读取数据是val值出现一次，Key++,若读取数据不是val，则Key–。

那么假设在X区间中，得到了某个数的出现次数大于X/2。

假设这是我们最终所求的val值，那么后面出现的val加上当前的Key必然大于了其他所有数的出现次数总和。（(:зゝ∠) 有兴趣的人可以想想是为什么，我前面有提示）。

假设这不是我们最终所求的val值，我们从最坏情况来考虑前X段除了我们得到的数a以外其他全是最终答案b，后面N-X的段除了b以外其他全是a

即假设数组为N，前X个为A个a和（X-A）个b （假设b为我们所求的最终答案，a为前X个里面得到的答案）

那么在后面一段中，b至少存在N/2+1-(X-A)个，a则至多存在N-X - （N/2+1-(X-A)）
那么我们将2A-X +N-X - （N/2+1-(X-A)） -（ N/2+1-(X-A)）

化简得到 -2。

这样我们就可以模拟一个栈，当栈内为空时，将读取的元素弹入栈内并设置cnt值为1，每当读取一个元素时，都将这个元素与栈内元素比较，如果相同则cnt++,不同则cnt–,当cnt=0时，将栈内元素弹出，将读取元素弹入。

最终的栈内元素则为所求。

所以算法得证。（只是我觉得，不敢保证，如果有错告诉我，我改）

最后贴一下代码：

/** 
 * 算法基础：摩尔投票法 
 * @param nums 
 * @return 
 */
 public int majorityElement(int[] nums) {  

int majority = -1;  

int count = 0;  

for (int num : nums) {  
    if (count == 0) {  
        majority = num;  
        count++;  
    } else {  
        if (majority == num) {  
            count++;  
        } else {  
            count--;  
        }  
    }  
}  
      return  majority;
}