题解 | #数组中出现次数超过一半的数字#
数组中出现次数超过一半的数字
https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param numbers int整型vector
* @return int整型
*/
int MoreThanHalfNum_Solution(vector<int>& numbers) {
// write code here
//使用摩尔投票
if(numbers.size() == 0)return -1;
pair<int,int> tmp;
tmp.first = numbers[0];
tmp.second = 0;
for(int& val: numbers){
if(val == tmp.first){
tmp.second += 1;
}else{
tmp.second -= 1;
if(tmp.second == 0){
tmp.first = val;
tmp.second = 1;
}
}
}
return tmp.first;
}
};
题解：该题使用摩尔投票。从头开始，如果遇到相同的数就加一表示出现次数加1，如果不同则减一，如果此时当前数出现为0，那么就要换候选人，其出现次数置为1。遍历完整个数组，最后的候选人即为出现次数超过一半的。时间复杂度是O(n),空间复杂度是O(1)。
投递水滴等公司10个岗位 >
），不要给自己挖坑
查看27道真题和解析