剑指offer 39 找一个众数

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

思路: 哈希

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int>mp;
        for(auto it : nums){
            mp[it]++;
            if(mp[it]>nums.size()/2) return it;
        }
        return 0;
    }
};

时间复杂度: N
空间复杂度: N

更好的思路: 摩尔投票法: 和自己相同的会给自己票数+1, 不相同的会给自己票数-1.
设当前的值可能是众数, 那么遇到下一个不是当前值的时, 统计-1, 并且跳到下下个值. 无论如何, 最终那个众数一定投票统计一定是>0的.
时间复杂度: N
空间复杂度: 1