Powered By GitBook
169.Majority Element

169.Majority Element

难度:Easy
给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在众数。
示例 1:
1
输入: [3,2,3]
2
输出: 3
Copied!
示例 2:
1
输入: [2,2,1,1,1,2,2]
2
输出: 2
Copied!
方法:
    最简单的是直接hash_map计数,数目最多的就是了。
    代码如下:
    1
    class Solution {
    2
    public:
    3
    int majorityElement(vector<int>& nums) {
    4
    unordered_map<int,int> cnt;
    5
    int len=nums.size();
    6
    for(int i=0; i<len;++i)
    7
    cnt[nums[i]]++;
    8
    int index=0;
    9
    for(int i=1;i<len;i++)
    10
    {
    11
    if(cnt[nums[i]]>cnt[nums[index]])
    12
    index=i;
    13
    }
    14
    return nums[index];
    15
    }
    16
    };
    Copied!
    摩尔投票法:核心是对拼消耗,既然我超过了总数的一半,那遇见一个不同的数就抵消,最后活下来的就是众数了。 代码如下:
    1
    class Solution {
    2
    public:
    3
    int majorityElement(vector<int>& nums) {
    4
    int major=nums[0];
    5
    int cnt=1;
    6
    for(int i=1;i<nums.size();i++)
    7
    {
    8
    if(major==nums[i])
    9
    cnt++;
    10
    else if(--cnt == 0)
    11
    major = nums[i+1];
    12
    }
    13
    return major;
    14
    15
    }
    16
    };
    Copied!
    代码中,当i的计数和i+1的计数相等时,major自动跳转到地i+1个数。
Last modified 2yr ago
Copy link