在论坛中寻找发帖数超过一半的ID（确实存在这样的ID）

如果你有一个当前论坛上的所有帖子（包括回帖）的列表，其中帖子作者的ID也在其中，你能快速找出发帖数超过一半的ID（成为“水王”）吗？

解法：

如果每次删除两个不同的ID（不管是否包含“水王”的ID），那么，在剩下的ID列表中，“水王”ID出现的次数仍然超过剩余总数的一半，可以通过

不断地重复这个过程，把ID列表中的ID总数降低（转化为更小的问题），从而得出答案。

代码如下：

#include<iostream>using namespace std;const int N=22;int *find(int *ID,int N);int main(){int ID[N];int i;for(i=0;i<N;i++)cin>>ID[i];int *candidate=find(ID,N);for(i=0;i<3;i++)cout<<candidate[i]<<" ";cout<<endl;delete []candidate;return 0;}int *find(int *ID,int N){int *candidate=new int[3];int nTimes[3]={0};int i,j,k;for(j=0;j<3;j++)candidate[j]=0;for(i=0;i<N;i++){for(j=0;j<3;j++){if(candidate[j]==ID[i]){nTimes[j]++;break;}}if(j==3){for(k=0;k<3;k++){if(nTimes[k]==0){candidate[k]=ID[i];nTimes[k]++;break;}}if(k==3){nTimes[0]--;nTimes[1]--;nTimes[2]--;}}}return candidate;

1楼zcm_xh2008昨天 18:01

博主，对于这个用例：n1,1,1,1,1,2,3,4,5,6,7,1,8,1,9,1n输出的结果应该是1吧，但是我使用你的第一个Find函数得到的结果是9

Re: jirongzi_cs2011昨天 22:03

回复zcm_xh2008n你没有看清题意，这里要求是超过一半，你这个例子是16个元素，1有8个，没有超过一半，根据我的算法，肯定是得到9.