169. Majority Element（众数）-蒲公英云

169. Majority Element（众数）

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

思路：

hash方法，遍历的同时插入。数据结构用unordered_map。注意当counter>n/2 才返回；
位图方法，int 32位，从第一位开始遍历每个数，每次判断该位的出现次数，大于n/2的就再与res或。最终返回res。事件复杂度较高。当再考虑移位时，考虑负数，所以要做无符号转换。
摩尔投票算法：因为该众数是在所有的数中出现了大于n/2次，所以至少两个数之间就会有一个这个数，所以通过从第一个数开始遍历到最后一个数，当前数==众数就+1，不是就-1，等到次数为0了，就重新赋值当前数。这样到最后返回该众数

综上，最快的还是1。因为1在部分案例下不需要完全遍历完。而其他的都需要遍历O(n)
代码1，

unordered_map<int,int> counter;
        int half= nums.size( )/2;
        for(auto i:nums)
        { 
            if(++counter[i] >half)      //因为需要大于一半：奇数的话不能等于。
            { 
                return i;
            }
        }
        return -1;

代码2：

int bits=0,res=0;
        int n=nums.size()/2;
        for(unsigned int i = 0, mask = 1; i < 32; i++, mask <<= 1)
        { 
            bits=0;
            for(auto a:nums)
            { 
                if(a & mask)
                     bits++;
            }
            if(bits>n)
            { 
                res|=mask;
            }
        }
        return res;
    }

代码3：

int count=0,majority;
        for(auto t:nums)
        { 
            if(!count)
                majority=t;
            count+= majority==t? 1:-1;
        }
        return majority;
    }