The Most Frequent Number-蒲公英云

The Most Frequent Number

" class="reference-link">The Most Frequent Number

时间限制(普通/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
#include

//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

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;
}