0
已解决
中级启示者
题目描述 Description
你需要在一组n个正整数的数据中，找出一个数，这个数在这组数据中出现次数大于⌊ n/2 ⌋.
输入描述 Input Description
第一行一个整数 n，表示数的个数。
第二行 n个正整数 ai,空格隔开
输出描述 Output Description
一行一个整数
WA60
#include<iostream>
#include<cstdio>
#include<algorithm>
#define reg register
using namespace std;
int n;
long long a[2000005];
int main(){
cin>>n;
for(reg int i=1;i<=n;i++) scanf("%lld",&a[i]);
sort(a+1,a+1+n);
int cnt=1;
for(reg int i=1;i<=n;i++){
if(a[i]==a[i+1]) cnt++;
else{
if(cnt>n/2){
cout<<a[i];
return 0;
}
cnt=1;
}
}
return 0;
}
汪恺恒在2021-05-26 18:01:19追加了内容
d
0
已采纳
初级光能
把sort去掉试试
0
资深守护
快排你试过吗？
快排：
void qsort(int left,int right){
//1排序结束标志
if(left>=right){
return;
}
//2确定基准值，扫描位置
int x=a[left],i=left,j=right;
//3持续扫描
while(i<j){
//3.1后--前
while(i<j&&a[j]>=x){
j--;
}
a[i]=a[j];
//3.2前--后
while(i<j&&a[i]<=x){
i++;
}
a[j]=a[i];
}
//4更新基准值的位置
a[i]=x;
//5递归
qsort(left,i-1);
qsort(i+1,right);
return;
}
ps:用桶他不香吗？
0
新手启示者
13行应该是i遍历1~n-1吧
如：
7
1 1 1 3 0 0 0
会输出0
0
被禁言
修练者
同意2楼！！！
