寻找发帖“水王”

编程之美第2.3题————寻找发帖“水王”

题目描述:

Tango是微软亚洲研究院的一个试验项目。研究院的员工和实习生们都很喜欢在Tango上面交流灌水。传说,Tango有一大“水王”,他不但喜欢发贴,还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子(包括回帖)的列表,其中帖子作者的ID也在表中,你能快速找出这个传说中的Tango水王吗?

首先,我们可以假设有这样一个数据结构来表示帖子

type struct post
{
    char* title;
    char* content;
    int uid;
}post_t;

题目告诉我们已知所有帖子的列表,也就是说我们知道了所有帖子的链表 post_t* post_list,或者是所有帖子的数组post_array[num]。然后让我们找到出现次数最多的uid是多少,并且该uid一定超过了总和的一半。为了叙述方便,下面用数组举例。最容易就想到的方法,就是遍历整个数组,记录每一个uid出现的次数,然后再比较一下,求出最大的。

其实,这个问题就可以等价于:求数组中出现次数大于一半的那个数

解法一

对数组排序,然后遍历排好序的数组,统计各ID出现的次数,找到超过一半的那个即可。代码如下:

int Find (int* post, int len)
{
    sort(post, post + len);

    int num = 1;
    for(int i = 0; i < len; i++)
    {
        if(post[i] == post[i + 1])
            num++;
        else
            num = 1;
        if(num > len / 2)
            return post[i];
    }
    return 0;
}

这里先调用了一下sort函数排序,也可以换成自己的排序函数。

因为采用了排序,复杂度有所提升,于是书中提出了第二种解法,我觉得是比较巧妙的。

解法二

由于x出现的次数大于总数的一半,所以如果每次删除两个不同的值,不管是否有x,在剩下的数中,x的次数依然会大于总数的一半。

于是,算法可以这样设计

int Find2 (int* post, int len)
{
    int x;
    int times = 0;
    for(int i = 0; i < len; i++)
    {
        if(times == 0)
        {
            x = post[i];
            times = 1;
        }
        else
        {
            if(x == post[i])
                times++;
            else
                times--;
        }
    }
    return x;
}

该算法不用排序,很巧妙的通过向前移动达到了“删除”的目的,自己真的没想到:)。

越来越觉得优美的代码就是美了,简洁明了,而又功能强大。

扩展问题:

随着Tango的发展,管理员发现,“超级水王”没有了。统计结果表明,有3个发帖很多的ID,他们的发帖数目都超过了帖子总数目N的1/4。你能从发帖ID列表中快速找出他们的ID吗?

解法x

这个思路就是一样的了,设a,b,c三人的发帖数都超过了 1/4,那么把4个不同id删除以后,并不影响剩余数组中a,b,c三人的发帖数都超过1/4这个结果。示意图如下所示。

QQ图片20130721232439

把数组分为四个四个数字一组的来看。由于a的发帖数超过了1/4,所以,平均下来,在每一个分组里都有一个a,并且至少在某一组中有大于一个的a,假如分组1中的四个数字都不相同,我们删除分组1,如果a不在分组1里面,那么在剩余的2~n组中,a出现的次数显然会继续大于1/4;如果a在分组1里面,那么在剩余2~n组中,平均下来,a还是会至少在每一个分组出现一次。所以只要分组1中4个数字不相同(主要是保证没有两个a),那么删除分组1,并不改变a在剩余数组中出现次数依然大于1/4的事实。同理b,c。

代码如下:

void Findx(int* post, int len)
{
    int a, b, c;
    int ta = 0;
    int tb = 0;
    int tc = 0;

    for(int i = 0; i < len; i++)
    {
        if(ta == 0)
        {
            a = post[i];
            ta++;
        }
        else if(a == post[i])
            ta++;
        else if(tb == 0)
        {
            b = post[i];
            tb++;
        }
        else if(b == post[i])
            tb++;
        else if(tc == 0)
        {
            c = post[i];
            tc++;
        }
        else if(c == post[i])
            tc++;
        else
        {
            ta--;
            tb--;
            tc--;
        }
    }

    cout << "a: " << a << "\t";
    cout << "b: " << b << "\t";
    cout << "c: " << c << "\t";
}

Enjoy!

Leave a Reply

Your email address will not be published.