题解 | #数组中出现次数超过一半的数字#
数组中出现次数超过一半的数字
https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163
摩尔投票法，因为题目保证有解所以最后可以免去验证的步骤
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
int res, cnt = 0;
for (auto &i: numbers) {
if (cnt == 0) {
res = i;
cnt++;
}
else if (res == i) cnt++;
else cnt--;
}
return res;
}
};
查看17道真题和解析