The Most Frequent Number

谁借莪１个温暖的怀抱￠ 2022-04-03 11:45 163阅读 0赞

## The Most Frequent Number ![分享至QQ空间][QQ] [![去爱问答提问或回答][iqa.gif]][iqa.gif 1] ##

时间限制(普通/Java):3000MS/9000MS 运行内存限制:1024KByte  
总提交: 165 测试通过: 41

描述

Seven (actually six) problems may be somewhat few for a contest. But I am really unable to devise another problem related to Fantasy Game Series. So I make up an very easy problem as the closing problem for this contest.

Given a sequence of numbers A, for a number X if it has the most instances (elements of the same value as X) in A, then X is called one of the most frequent numbers of A. Now a sequence of numbers A of length L is given, and it is assumed that there is a number X which has more than L / 2 instances in A. Apparently X is the only one most frequent number of A. Could you find out X with a very limited memory?

输入

Input contains multiple test cases. Each test case there is one line, which starts with a number L (1 <= L <= 250000), followed by L numbers (-2^31 ~ 2^31-1). Adjacent numbers is separated by a blank space.

输出

There is one line for each test case, which is the only one most frequent number X.

样例输入

5 2 1 2 3 2
    8 3 3 4 4 4 4 3 4

样例输出

2
    4

题目来源

[Online Contest of Fantastic Game][]

\#include<stdio.h>  
\#include<stdlib.h>  
  
  
//set up all the data structure and variables for answer  
struct Node  
\{  
int e, n;//e for element, n for number  
Node \*next;  
\};  
  
  
int x; //x for the most frequent number  
int l; //l for length  
Node \*A;  
  
  
int main()  
\{  
//set up the variables for manipulation  
int e;  
Node \*p,\*q,\*r;//p for iternation. before p moves to the next, q save the status of p. r for new added node.  
A=NULL;  
while(scanf("%d",&l)==1)//if use "if" here -> wrong answer  
\{  
//printf("Debug:l=%d", l);  
//set up the first node  
scanf("%d",&e);  
A=(Node\*)malloc(sizeof(Node));  
A->e=e;  
A->n=1;  
A->next=NULL;  
l--;  
  
  
//set up the following nodes  
while(l>0)//can not put scanf here  
\{  
scanf("%d",&e);  
p=A;  
//iterate the linked list. if e existes, then plus 1, else add node  
while(p!=NULL)  
\{  
if(p->e==e)  
\{  
p->n=p->n+1;//can not use ++ or += here  
//printf("Debug:p->n = %d", p->n);  
break;  
\}  
q=p;p=p->next;  
\}  
if(p==NULL)  
\{  
r=(Node\*)malloc(sizeof(Node));  
r->e=e;  
r->n=1;  
r->next=NULL;  
q->next=r;  
\}  
l--;  
\}  
  
  
  
//search the most frequent number and output  
int maxn=0;  
p=A;  
while(p!=NULL)  
\{  
if((p->n)>maxn)  
\{  
maxn=p->n;  
x=p->e;  
\}  
p=p->next;  
\}  
  
  
printf("%d\\n",x);  
  
  
//ATTENTION!!! free the memory!!  
p=A;  
while(p!=NULL)  
\{  
q=p;p=p->next;  
free(q);  
\}  
A=NULL;  
\}  
return 0;  
\}

//简单的

\#include <stdio.h>  
  
  
int main()  
\{  
int n;  
while (scanf("%d", &n) != EOF)  
\{  
int ans, cnt = 0, x;  
for (int i = 0; i < n; ++ i)  
\{  
scanf("%d", &x);  
if (cnt == 0)  
\{  
ans = x;  
cnt = 1;  
\}  
else if (x == ans)  
\++ cnt;  
else  
\-- cnt;  
\}  
printf("%d\\n", ans);  
\}  
return 0;  
\}

[QQ]: http://acm.tzc.edu.cn/acmhome/forum/images/ico_qzone.gif
[iqa.gif]: http://acm.tzc.edu.cn/acmhome/forum/images/iqa.gif
[iqa.gif 1]: http://iqa.tzc.edu.cn/c-5.html
[Online Contest of Fantastic Game]: http://acm.tzc.edu.cn/acmhome/search.do?method=simpleSearch&searchFrom=Source&queryString=Online+Contest+of+Fantastic+Game