题目链接:
方法一:
若数组中有数字的出现次数超过数组长度的一半(绝对众数),则将该数组排序后中间位置的数一定就是该数。
class Solution {
public:
int moreThanHalfNum_Solution(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
return nums[n / 2];
}
};
方法二、摩尔投票算法
用于解决绝对众数问题,主要思想为:“捉对厮杀”
维护一个变量val,初始化为数组的第一个元素,cnt用于记录val的出现次数,初始时为1。从前到后遍历数组,如果元素和val相同就将cnt++,表示出现次数+1,否则就将val赋值为当前元素并将cnt更新为1。由于绝对众数的出现次数大于数组长度的一半,其出现次数在经过如此的“抵消”过程后一定>0,val最后的值即为绝对众数。
class Solution {
public:
int moreThanHalfNum_Solution(vector<int>& nums) {
int cnt = 1, val = nums[0];
for (int i = 1; i < nums.size(); i++) {
if (val == nums[i]) cnt++;
else cnt--;
if (cnt == 0) {
val = nums[i];
cnt = 1;
}
}
return val;
}
};
标签:cnt,val,nums,int,次数,数组,P52
From: https://www.cnblogs.com/pangyou3s/p/17964193