Majority Element
1,题目要求
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
给定大小为n的数组,找到多数元素。 多数元素是出现超过⌊n /2⌋倍的元素。
您可以假设该数组非空,并且多数元素始终存在于数组中。
2,题目思路
对于这道题,要求找出一个数组中的众数,也即出现次数超过n/2的数字。
比较简单和直观的个人思路是,直接定义一个map结构,找到每个数字出现的次数,然后再遍历一次,出现次数最多的就一定是众数了。
这个方法可行,但是需要额外空间,而且需要对数组遍历两遍,不是太好。
另外一种比较好的方法,则是Moore Voting,即摩尔投票法。
这种方法的思路是,首先将第一个数字设置为众数,然后将计数器设置为1,比较下一个数字是否相等:
- 如果相等,则计数器加一;
- 如果不相等,就将计数器减一;
然后此时观察计数器的值,如果计数器此时为0,就将下一个值设为候选的众数。
这样,遍历到最后,就可以找到众数了。
这个方法有一个前提,就是数组中一定要存在众数的。实现策略则是,如果计数器减到0了话,说明目前不是候选者数字的个数已经跟候选者的出现个数相同了,那么这个候选者已经很weak,不一定能出现超过半数,我们选择更换当前的候选者。
3,代码实现
- 利用map实现
static auto speedup = [](){
ios::sync_with_stdio(false);
cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int, int> hashMap;
int maxNum = 0;
int res = 0;
for(auto &n : nums)
hashMap[n]++;
for(auto &hm : hashMap)
{
if(hm.second > maxNum)
{
res = hm.first;
maxNum = hm.second;
}
}
return res;
}
};
- moore voting
int x = []() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
return 0;
}();
class Solution {
public:
int majorityElement(vector<int>& nums) {
int mooreCounter = 1;
int major = nums[0];
for (int i = 1; i < nums.size(); i++)
{
if (mooreCounter == 0)
{
mooreCounter++;
major = nums[i];
}
else if (major == nums[i])
{
mooreCounter++;
}
else
{
mooreCounter--;
}
}
return major;
}
};