很巧妙的算法,自愧不如啊
当初就想着二分啊二分,结果还是没有分出来,而且情况很复杂
下面的代码的算法很巧妙,充分利用了有一个数出现的次数大于总数的一半这一条性质
1 #include<stdio.h>
2 int main()
3 {
4 int i,counter,answer,n,data;
5 while(scanf("%d",&n)!=EOF)
6 {
7 counter=0;
8 for(i=1;i<=n;i++)
9 {
10 scanf("%d",&data);
11 if (counter == 0)
12 {
13 answer=data;
14 counter=1;
15 }
16 else if (answer == data)
17 {
18 counter++;
19 }
20 else
21 counter--;
22 }
23 printf("%d\n",answer);
24 }
25 return 0;
26 }