重复元素问题

Question

一道笔试题，时间复杂度要求O(N)int数组中有三个元素出现的次数超过元素总个数的1/4,在规定时间复杂度下，求出这三个数。我的思路，交卷的一刹那，我发现自己考虑非常不全面。定义三个变量，保存三个数，在定义三个计数器，开始把a[0],a[1],a[2]赋给三个变量（这里有问题，万一重复了），然后对后面的数组扫描，出现相等的计数器加一，不相等计数器减一。已经通知下午2点面试，晚上再跟大家探讨下，这题其实跟数组中有元素超过数组一半是一类问题吧，可能考虑起来要复杂点。请用C/C++实现，Java我不熟。

Answer 1

//多谢@zonxin@brayden这是编程之美寻找发帖水王扩展问题，代码如下，参考网址
voidfind3(int*ID,intn)
{
intcandidate[3];
intnTimes[3]={0};
inti;
for(i=0;i{
if(nTimes[0]==0)
{
if(ID[i]==candidate[1])
nTimes[1]++;
elseif(ID[i]==candidate[2])
nTimes[2]++;
else
{
candidate[0]=ID[i];
nTimes[0]++;
}
}
elseif(nTimes[1]==0)
{
if(ID[i]==candidate[0])
nTimes[0]++;
elseif(ID[i]==candidate[2])
nTimes[2]++;
else
{
candidate[1]=ID[i];
nTimes[1]++;
}
}
elseif(nTimes[2]==0)
{
if(ID[i]==candidate[0])
nTimes[0]++;
elseif(ID[i]==candidate[1])
nTimes[1]++;
else
{
candidate[2]=ID[i];
nTimes[2]++;
}
}
else
{
if(ID[i]==candidate[0])
nTimes[0]++;
elseif(ID[i]==candidate[1])
nTimes[1]++;
elseif(ID[i]==candidate[2])
nTimes[2]++;
else
nTimes[0]--,nTimes[1]--,nTimes[2]--;
}
}
printf("三个水王ID分别是:%d,%d,%d\n",candidate[0],candidate[1],candidate[2]);
}