题目来自《编程之美》
这里自己写了下寻找一个最多的ID和寻找2个最多的ID的情况，注意条件（一个最多的ID发帖量必须超过总帖的1/2,2个最多的ID发帖量各自都超过总帖数的1/3 才能用如下的方法解答）
扩展题目可以按照代码思路类推。
代码可以直接运行。
/*
* Description:
* 寻找发帖最多的1个（2个）ID。
* Author :FinL
* Language: C
* Date : 2010-09-20
*/
#include
int candidate;
int candidate1;
int candidate2;
/*其中有一个人的帖子超过了一半*/
int find(int *a,int n)
{
int i,ntimes;
for(i=ntimes=0;i
{
if(0==ntimes)
{
candidate=a[i];
ntimes=1;
}
else
{
if(a[i]==candidate)
ntimes++;
else
ntimes--;
}
}
return candidate;
}
/*其中有2个人的帖子各超过了1/3*/
void find2(int *a,int n)
{
int i,ntimes1=0,ntimes2=0;
for(i=0;i
{
if(0==ntimes1)
{
candidate1=a[i];
ntimes1=1;
}
else
{
if(a[i]==candidate1)
{
ntimes1++;
}
else
{
if(0==ntimes2)
{
candidate2=a[i];
ntimes2=1;
}
else
{
if(a[i]==candidate2)
{
ntimes2++;
}
else
{
ntimes1--;
ntimes2--;
}
}
}
}
}
}
int main()
{
int a[]={1,1,1,1,2,2,2,2,3,3};
int n;
// int candidate;
n=sizeof(a)/sizeof(a[0]);
// candidate=find(a,n);
find2(a,n);
printf("candidate is %d,%d\n",candidate1,candidate2);
return 0;
}
阅读(1002) | 评论(0) | 转发(0) |
