已知一个数出现的次数超过了一半,请用O(n)的复杂度的算法找出这个数

2023-04-24,,

#include<iostream>
using namespace std;
//#define maxn 2000010
#include<stdio.h>
//int a[maxn];
//int val[maxn];
int main(){
int t;
scanf("%d",&t);
int i;
// memset(val,0,sizeof(val));
int k=2*t;
int v,temp,count;
scanf("%d",&v);
count=1;
for(i=1;i<k;i++){
scanf("%d",&temp);
if(temp!=v&&count==0){
v=temp;count=1;}
else if(temp!=v){
count--;
}
else count++;
}
if(count>=2)printf("%d\n",v);
else printf("-1\n");
return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

已知一个数出现的次数超过了一半,请用O(n)的复杂度算法找出这个数的相关教程结束。

《已知一个数出现的次数超过了一半,请用O(n)的复杂度的算法找出这个数.doc》

下载本文的Word格式文档,以方便收藏与打印。