169. Majority Element（众数）

ゞ浴缸里的玫瑰 2023-07-18 14:26 19阅读 0赞

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

思路：

1.  hash方法，遍历的同时插入。数据结构用unordered\_map。注意当counter>n/2 才返回；
2.  位图方法，int 32位，从第一位开始遍历每个数，每次判断该位的出现次数，大于n/2的就再与res或。最终返回res。事件复杂度较高。当再考虑移位时，考虑负数，所以要做无符号转换。
3.  摩尔投票算法：因为该众数是在所有的数中出现了大于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;
        }