问题描述:3个发帖人,每人发帖数在总数的1/4以上,即剩下的帖子总数不及其中任何一个人所发帖的数目。
思路:和水王思路相似,采取三个计数值。见相等ID则计数值递增,见未出现的ID且计数值不为0则递减,计数值为0则引入新ID,最后的三个ID即为结果
易错点:需要考虑避开这样的情况,当ID为{1, 1, 1}时,需要让计数值为{3,0,0},而非{1,1,1}即重复的不计到不同的计数值上去
这样一来代码实际上是蛮简单的
#include <stdio.h>
typedef int Type;
void Find(Type *ID, int N, Type *ret)
{
int nTime1, nTime2, nTime3, i;
for (i=nTime1=nTime2=nTime3=0; i<N; ++i) {
if (ID[i] == ret[0]) {
nTime1++;
} else if (ID[i] == ret[1]) {
nTime2++;
} else if (ID[i] == ret[2]) {
nTime3++;
}
else if (nTime1 == 0) {
ret[0] = ID[i];
nTime1++;
}
else if (nTime2 == 0) {
ret[1] = ID[i];
nTime2++;
}
else if (nTime3 == 0) {
ret[2] = ID[i];
nTime3++;
}
else {
nTime1--;
nTime2--;
nTime3--;
}
}
}
int main(int argc, char *argv[])
{
int rand[11] = {1, 1, 1, 3, 4, 4, 4, 5, 6, 5, 5};
int ret[3]={0, 0, 0};
Find(rand, 11, ret);
for (int i = 0; i<3; ++i) {
printf("%d\n", ret[i]);
}
return 0;
}
编译命令:gcc -o findmost findmostID3.c -Wall -g -std=c99
在gcc version 4.4.3 (Ubuntu 4.4.3-4ubuntu5.1) 下验证
参考文章:
http://blog.csdn.net/rein07/article/details/6741661