# 重复元素问题-问答-阿里云开发者社区-阿里云

## 重复元素问题

int数组中有三个元素出现的次数超过元素总个数的1/4,在规定时间复杂度下，求出这三个数。

a123456678 2016-06-08 20:59:43 1826 0
1 条回答

• ``````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]);
}``````
2019-07-17 19:32:44
赞同 展开评论 打赏

516
1
0
498
1
0
472
1
0
651
1
0
1462
1
0
1100
1
0
389
1
0
1351
1
0
308
1
0
532
0
0