169、多数元素(简单)

题目要求：时间复杂度O(n)、空间复杂度O(1)

简单题都做不了。。。：

解题思路：

摩尔投票法：

核心就是对拼消耗。玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。

最后能剩下的必定是自己人。

换句话说就是，从第一个元素开始计数，遇到相同的count+1，遇到不同的count-1，如果count到0了那么就需要更换当前元素。

class Solution {
    public int majorityElement(int[] nums) {
        int ret = nums[0];
        int count  =1;
        for(int num : nums){
            if(num != ret){
                count--;
                if(count == 0){
                    count = 1;
                    ret = num;
                }
            }else{
                count++;
            }
        }
        return ret;
    }
}