找出数组中出现次数超过一半的数字
2021-03-20 15:25
标签：class hal res span time nbsp 一半 复杂 时间 思路： 一般我们会想到用排序，然后找出中间那个值，此值就是超过一半的那个数 但是这样的时间复杂度一般为O(nlogn) 其实有一个比较巧妙的办法，时间复杂度为O(n) 1,遍历这个数组，如果之前一个数字和下一个数字重复则+1，否则-1 这样最终留下的数就是那个超过一半的那个数 代码 找出数组中出现次数超过一半的数字 标签：class hal res span time nbsp 一半 复杂 时间 原文地址：https://www.cnblogs.com/dongma/p/13923286.htmlvoid moreThanHalf(int* arr,int len){
int result = arr[0];
int times = 1;
for (int i = 1; i i) {
if(times == 0){
result = arr[i];
times=1;
continue;
}
if(result == arr[i]){
times++;
} else{
times--;
}
}
coutendl;
}
上一篇：python判断函数收集
下一篇：springmvc中文乱码