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