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个数。