勤能补拙,厚积薄发

合抱之木,生于毫末;九层之台,起于垒土;千里之行,始于足下
随笔 - 19, 文章 - 0, 评论 - 3, 引用 - 0
数据加载中……

编程之美2.3扩展:寻找3个发帖数>1/4*sum的发帖人

问题描述: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

posted on 2012-08-12 10:26 lee007 阅读(488) 评论(0)  编辑 收藏 引用 所属分类: Programming Study


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理