Comment on page
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个数。
Last modified 1yr ago