求比较好的算法
输入由多组数据组成。每组数据由二行组成，第一行是整数n(1<=n<=100000), 第二行是n个空格分开的整数，它们的值位于区间。
题目保证60%的数据n的值不超过20。
输出
每一组输入数据输出一行。如果存在满足条件的x，则输出，否则输出-1。
样例输入 Copy
3
3 2 3
8
0 5 5 3 5 7 5 5
8
0 5 5 3 5 1 5 7 不知道是不是你需要的
#include<stdio.h>
int main(){
int i,j,n,max,a,b={0};
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d",&a);
for(i=0;i<n;i++)b]++;
max=b;
for(i=0;i<10;i++){
if(b&&b>max){
max=b;
j=i;
}
}
if(max>n/2)printf("%d\n",j);
else printf("-1");
return 0;
} basketmn 发表于 2022-2-9 14:48
不知道是不是你需要的
它们的值位于区间。 jhq999 发表于 2022-2-9 14:58
它们的值位于区间。
这。。。
计算量有点大 basketmn 发表于 2022-2-9 15:12
这。。。
计算量有点大
所以想求比较好的算法 int main()
{
int count=0,i=0,j=0;
scanf("%d",&count);
int *a=(int*)malloc(sizeof(int)*count);
for(i=0;i<count;i++)scanf("%d",&a);
int flag=-1,tmp=0,bigin=0;
for(i=0;i<count;i++)
{
for(j=i+1;j<count;j++)
{
if(a>a)tmp=a,a=a,a=tmp;
}
if ((i&&a!=a))
{
if (i-bigin>count/2)
{
flag=a;
break;
}
bigin=i;
}
}
if (i==count)
{
if(i-bigin>count/2)
{
flag=a;
}
}
printf("%d",flag);
free(a);
return 0;
} 我的代码只用到一个 while 循环，时间复杂度是：O(n)。
想看看其他大佬代码，学习学习#include <stdio.h>
int main()
{
int n, count = 0, num, res;
scanf("%d", &n);
/*----- 摩尔投票法 -----*/
while(n--){
scanf("%d", &num);
if(!count) res = num;
res == num ? count++ : count--;
}
count ? printf("%d", res) : printf("%d", -1);
return 0;
} 傻眼貓咪 发表于 2022-2-9 18:12
我的代码只用到一个 while 循环，时间复杂度是：O(n)。
想看看其他大佬代码，学习学习
玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。最后能剩下的必定是自己人。
你这个应该是最简单的了吧？
0 5 5 3 5 7 5 5
5 res=5 1
5 2
7 1
5 2
3 1
5 2
5 3
0 2
0 5 5 3 5 1 5 7
7 res=7 1
5 0
1 res=1 1
5 0
3 res=3 1
5 0
5res=5 1
0 0
页:
[1]