寻找发帖水王
时间：2010-09-20 来源：wsnhyjj
题目来自《编程之美》
这里自己写了下寻找一个最多的ID和寻找2个最多的ID的情况，注意条件（一个最多的ID发帖量必须超过总帖的1/2,2个最多的ID发帖量各自都超过总帖数的1/3 才能用如下的方法解答）
扩展题目可以按照代码思路类推。 代码可以直接运行。 /* * Description: * 寻找发帖最多的1个（2个）ID。 * Author :FinL * Language: C * Date : 2010-09-20 */
#include<stdio.h>
int candidate; int candidate1; int candidate2;
/*其中有一个人的帖子超过了一半*/ int find(int *a,int n) { int i,ntimes; for(i=ntimes=0;i<n;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<n;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;
}
扩展题目可以按照代码思路类推。 代码可以直接运行。 /* * Description: * 寻找发帖最多的1个（2个）ID。 * Author :FinL * Language: C * Date : 2010-09-20 */
#include<stdio.h>
int candidate; int candidate1; int candidate2;
/*其中有一个人的帖子超过了一半*/ int find(int *a,int n) { int i,ntimes; for(i=ntimes=0;i<n;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<n;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;
}
相关阅读 更多 +
