题解 | 数组中出现次数超过一半的数字
数组中出现次数超过一半的数字
https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=295&tqId=23271&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int>& numbers) {
if (numbers.empty()) return 0;
int candidate = numbers[0];
int count = 1;
// 第一遍遍历：找出候选数字
for (int i = 1; i < numbers.size(); i++) {
if (count == 0) {
candidate = numbers[i];
count = 1;
} else if (numbers[i] == candidate) {
count++;
} else {
count--;
}
}
// 第二遍遍历：验证候选数字确实超过一半
// 虽然题目保证有解，但为了代码健壮性还是验证一下
count = 0;
for (int num : numbers) {
if (num == candidate) {
count++;
}
}
return count > numbers.size() / 2 ? candidate : 0;
}
};
哈希表:哈希集合和哈希映射 文章被收录于专栏
简单来说，哈希就是一个将任意长度数据“浓缩”成唯一固定长度“指纹”的单向过程。它在确保数据安全、实现高效数据结构和维护系统完整性方面，扮演着不可或缺的角色。
