[已解决]求比较好的算法

牵风

输入由多组数据组成。
每组数据由二行组成，第一行是整数n(1<=n<=100000), 第二行是n个空格分开的整数，它们的值位于区间[0,1000000000]。
题目保证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

最佳答案

月排行榜 / 总排行榜

傻眼貓咪

2022-2-9 18:12:32

我的代码只用到一个 while 循环，时间复杂度是：O(n)。
想看看其他大佬代码，学习学习

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.     int n, count = 0, num, res;
   
6.     scanf("%d", &n);
   
7.     /*----- 摩尔投票法 -----*/
   
8.     while(n--){
   
9.         scanf("%d", &num);
   
10.         if(!count) res = num;
    
11.         res == num ? count++ : count--;
    
12.     }
    
13.     count ? printf("%d", res) : printf("%d", -1);
    
14.     return 0;
    
15. }

复制代码

跳转到最佳答案楼层

basketmn

不知道是不是你需要的

1. #include<stdio.h>
   
2. int main(){
   
3.         int i,j,n,max,a[256],b[10]={0};
   
4.         scanf("%d",&n);
   
5.         for(i=0;i<n;i++)scanf("%d",&a[i]);
   
6.         for(i=0;i<n;i++)b[a[i]]++;
   
7.         max=b[0];
   
8.         for(i=0;i<10;i++){
   
9.                
   
10.                 if(b[i]&&b[i]>max){
    
11.                         max=b[i];
    
12.                         j=i;
    
13.                 }
    
14.         }
    
15.         if(max>n/2)printf("%d\n",j);
    
16.         else printf("-1");
    
17.         return 0;
    
18. }

复制代码

jhq999

basketmn 发表于 2022-2-9 14:48
不知道是不是你需要的

它们的值位于区间[0,1000000000]。

basketmn

jhq999 发表于 2022-2-9 14:58
它们的值位于区间[0,1000000000]。

这。。。
计算量有点大

牵风

basketmn 发表于 2022-2-9 15:12
这。。。
计算量有点大

所以想求比较好的算法

jhq999

1. int main()
   
2. {
   
3.         int count=0,i=0,j=0;
   
4.         scanf("%d",&count);
   
5.         int *a=(int*)malloc(sizeof(int)*count);
   
6.         for(i=0;i<count;i++)scanf("%d",&a[i]);
   
7.         int flag=-1,tmp=0,bigin=0;
   
8.         for(i=0;i<count;i++)
   
9.         {
   
10. 
    
11.                 for(j=i+1;j<count;j++)
    
12.                 {
    
13.                         if(a[i]>a[j])tmp=a[i],a[i]=a[j],a[j]=tmp;
    
14. 
    
15.                 }
    
16.                 if ((i&&a[i-1]!=a[i]))
    
17.                 {
    
18.                         if (i-bigin>count/2)
    
19.                         {
    
20.                                 flag=a[i-1];
    
21.                                 break;
    
22.                         }
    
23.                         bigin=i;
    
24.                 }
    
25.         }
    
26.         if (i==count)
    
27.         {
    
28.                 if(i-bigin>count/2)
    
29.                 {
    
30.                         flag=a[i-1];
    
31. 
    
32.                 }
    
33. 
    
34.         }
    
35.         printf("%d",flag);
    
36.         free(a);
    
37.         return 0;
    
38. }

复制代码

傻眼貓咪

我的代码只用到一个 while 循环，时间复杂度是：O(n)。
想看看其他大佬代码，学习学习

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.     int n, count = 0, num, res;
   
6.     scanf("%d", &n);
   
7.     /*----- 摩尔投票法 -----*/
   
8.     while(n--){
   
9.         scanf("%d", &num);
   
10.         if(!count) res = num;
    
11.         res == num ? count++ : count--;
    
12.     }
    
13.     count ? printf("%d", res) : printf("%d", -1);
    
14.     return 0;
    
15. }

复制代码

jhq999

傻眼貓咪 发表于 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