169.Majority Element

169.Majority Element

难度:Easy

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

方法：

• 最简单的是直接hash_map计数，数目最多的就是了。 代码如下:

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> cnt;
        int len=nums.size();
        for(int i=0; i<len;++i)
            cnt[nums[i]]++;
        int index=0;
        for(int i=1;i<len;i++)
        {
            if(cnt[nums[i]]>cnt[nums[index]])
                index=i;
        }
        return nums[index];
    }
};

• 摩尔投票法：核心是对拼消耗，既然我超过了总数的一半，那遇见一个不同的数就抵消，最后活下来的就是众数了。 代码如下:

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

代码中，当i的计数和i+1的计数相等时，major自动跳转到地i+1个数。