题解 | #数组中出现次数超过一半的数字#
数组中出现次数超过一半的数字
https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163
2022.0808算法第17题数组中出现次数超过一半的数字
这道题有多种解法，哈希表法、排序法、BM投票法等
哈希表法记录每个元素出现的次数，最后找出次数大于size/2的元素
排序法直接选择排序后中间位置的数字即可
BM投票法是将相邻两个元素判断是否相等，如果相等则计数+1，否则计数-1；
当计数==0时，更新候选元素，
这样在最后剩下的候选元素就是次数超过一半的数字；
首先定义候选元素，并计数
int cand=numbers[0]; int count=1;然后遍历数组，更新计数和候选元素
for(int i=1;i<numbers.size();i++){
if(cand==numbers[i])
count++;
else
count--;
if(count==0){
cand=numbers[i];
count=1;
}
}
查看14道真题和解析