探索云世界
一道笔试题，时间复杂度要求O(N)
int数组中有三个元素出现的次数超过元素总个数的1/4,在规定时间复杂度下，求出这三个数。
我的思路，交卷的一刹那，我发现自己考虑非常不全面。
定义三个变量，保存三个数，在定义三个计数器，开始把a[0],a[1],a[2]赋给三个变量（这里有问题，万一重复了），然后对后面的数组扫描，出现相等的计数器加一，不相等计数器减一。
已经通知下午2点面试，晚上再跟大家探讨下，这题其实跟数组中有元素超过数组一半是一类问题吧，可能考虑起来要复杂点。
请用C/C++实现，Java我不熟。
写回答
void find3(int * ID, int n)
{
int candidate[3];
int nTimes[3] = {0};
int i;
for (i = 0; i < n; i++)
{
if(nTimes[0] == 0)
{
if(ID[i] == candidate[1])
nTimes[1]++;
else if (ID[i] == candidate[2])
nTimes[2]++;
else
{
candidate[0] = ID[i];
nTimes[0]++;
}
}
else if (nTimes[1] == 0)
{
if(ID[i] == candidate[0])
nTimes[0]++;
else if (ID[i] == candidate[2])
nTimes[2]++;
else
{
candidate[1] = ID[i];
nTimes[1]++;
}
}
else if (nTimes[2] == 0)
{
if(ID[i] == candidate[0])
nTimes[0]++;
else if (ID[i] == candidate[1])
nTimes[1]++;
else
{
candidate[2] = ID[i];
nTimes[2]++;
}
}
else
{
if(ID[i] == candidate[0])
nTimes[0]++;
else if(ID[i] == candidate[1])
nTimes[1]++;
else if(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]);
}版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
