首页 > 代码库 > 在O(n)时间复杂度内找到出现超过一半的数
在O(n)时间复杂度内找到出现超过一半的数
#include<iostream> using namespace std; bool solver(const int a[],const int n, int & num) { if(NULL == a || 0>= n) return false; ////注意,是小写~ int count = 0; int com = a[0]; for(int i = 1;i<n;i++) { if(0 == count) { com = a[i]; count++; } else{ if(a[i] == com) count++; else count--; } } num = com; return true; } int main() { int a[] = {1,2,3,3,3,3,3,3,4}; int temp; solver(a,9,temp); cout<<temp; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。