2020-03-13 刷题1 (数组）

169 多数元素

标签：数组，众数
一共n个元素，其中出现了大于n/2次的元素被称为众数，给定数组中一定存在众数，把这个数找出来。

比较好想的方法包括，哈希表计数法，排序然后找第n/2+1的元素。有点tricky的方法就是摩尔投票法：

那么设置一个candidate以及其获得票数count，如果count为0，那么当前遍历到的元素就可以作为candidate并获得一票；如果count不为0，并且当前元素与candidate相同，再获得一票；不相等，则减掉一票。最后遍历完这个数组，candidate就一定是众数。

假设一共有2n+1个元素，其中众数a有n+1个，剩下的元素全为b（这是最坏的情况）。如果第一个元素是a，那么它一共可以获得支持票n+1，反对票n，最后必然剩下一票。而如果剩下的元素不全相等，它们内部就可以互相投反对票，a最终剩下的支持票就会更多。

上面是奇数个元素的情况，如果是偶数个的情况，剩下的支持票也会更多。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate, count = 0;
        for(int i = 0; i < nums.size(); i++){
            if(count == 0){
                candidate = nums[i];
                count++;
            }
            else{
                if(nums[i] != candidate)
                    count--;
                else count++;
            }
        }
        return candidate;
    }
};