编程之美2.3笔记:寻找发帖“水王”

降低问题规模的思想
服务器君一共花费了703.607 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

《编程之美》2.3:

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

当面试的时候我们遇到这样的问题,应该怎么去思考呢?读SICP的一个很大的收获是,学会抽象。

抽象

抽象就是从问题中提取有用的,本质的特征,然后将问题用一个简洁但包含同样信息的模型表示出来。复杂的问题经抽象后,可能会变成一个简单的问题,也可能会变成一个曾经遇到的问题,当然也可能仍然是复杂的问题。不管抽象后得到的结果是哪一种,看着抽象后的问题,想出解的可能性必然比直接看原题想的可能性大。

将这题抽象下就是:给你一个数组,里面有超过一半的数字是一样的,你的任务就是找出这个数字。

关于数字数组的处理,容易联想到的方法是排序或者哈希。那么将这些方法套到问题上,就可以得到:

  1. 排序后,直接输出中位数;
  2. 建立一个大哈希表(数字的值就是它在哈希表中的下标),遍历一次数组,将数都放到哈希表中,在这个过程中,如果发现哪个数的碰撞次数超过一半,就找到了。

这就是将问题抽象后的好处——容易进行知识迁移。

分析与解答

最直接的方法就是对数组中所有的数字排序,然后再扫描一遍,统计各个数字出现的次数,如果某个数字出现的次数超过一半,则输出这个数字。显然这个算法的时间复杂度是O(N * log2N + N)。

事实上,假如现在数组已经有序,那么数组中间的数字一定是这个要求的数字,所以根本不必扫描。此时算法的时间复杂度是O(N * log2N + 1)。那还能不能再简化一些呢?

我们看到,算法主要的消耗在排序这块,那能否跳过排序这个步骤呢?我们这样想,假如每次删除两个不同的数(不管包括不包括最高频数),那么,在剩下的数字里,原最高频数出现的频率一样超过了50%,不断重复这个过程,最后剩下的将全是同样的数字,即最高频数。此算法避免的排序,时间复杂度只为O(N)。

代码如下:

#include "stdio.h"

int FindFloodKing(int num[], int n)
{
    int i;
    int candidate = 0;
    int count = 0;
    for (i = 0; i < n; i++)
    {
        if (count == 0)
        {
            candidate = num[i];
            count = 1;
            printf("%d candidate = %d \n", i, candidate);
        }
        else
        {
            if (candidate == num[i])
            {
                count++;
                printf("%d candidate %d == num[i] %d, count自增为 %d \n", i, candidate, num[i], count);
            }
            else
            {
                count--;
                printf("%d candidate %d != num[i] %d, count自减为 %d \n", i, candidate, num[i], count);
            }
        }
    }
    return candidate;
}

int main()
{
    int i, n, rs;
    int arr[] = {9,11,11,13,11,11,11,18,19,11,11,20,11};
    n = sizeof(arr)/sizeof(int);
    rs = FindFloodKing(arr, n);
    printf("%d", rs);
}

程序运行为:

0 candidate = 9
1 candidate 9 != num[i] 11, count自减为 0
2 candidate = 11
3 candidate 11 != num[i] 13, count自减为 0
4 candidate = 11
5 candidate 11 == num[i] 11, count自增为 2
6 candidate 11 == num[i] 11, count自增为 3
7 candidate 11 != num[i] 18, count自减为 2
8 candidate 11 != num[i] 19, count自减为 1
9 candidate 11 == num[i] 11, count自增为 2
10 candidate 11 == num[i] 11, count自增为 3
11 candidate 11 != num[i] 20, count自减为 2
12 candidate 11 == num[i] 11, count自增为 3
11
  1. 先让candidate等于num[1],candidate = 9
  2. candidate (9) != num[2] (11),所以9和11都丢弃,重新让candidate = num[3] (11)
  3. 反复这个步骤,遇到不同的就丢弃,遇到相同的就用count来记录累计数。目的就是要丢弃掉尽可能多对不同的数字,最后剩下的就是“水数”。

在这个题目中,有一个计算机科学中很普遍的思想,就是如何把一个问题转化为规模较小的若干个问题。分治、递推和贪心等都是基于这样的思路。在转化过程中,小的问题跟原问题本质上一致。这样,我们可以通过同样的方式将小问题转化为更小的问题。因此,转化过程是很重要的。像上面这个题目,我们保证了问题的解在小问题中仍然具有与原问题相同的性质:水王的ID在ID列表中的次数超过一半。转化本身计算的效率越高,转化之后问题规模缩小得越快,则整体算法的时间复杂度越低。

特性利用

特性利用,就是根据问题的特点,定制一个解法。通常来说,这个特制的解法是最优的。使用这种思想需要先找出问题的特点,然后思考是什么导致特点的出现,以及思考特点的使用方法。最后,如果能得到想法,就可以为问题定制一个解法。

在“寻找水王”,即上面提到的问题中,显著的特点是有一个数的出现次数超过一半。从出现次数超过一半的原因的角度思考得不到启发。但是从利用这个特性的角度思考就会得到这样的启发:这个数出现的次数比剩下的数的出现次数总和还要多。将出现次数做减法,剩下的必然是出现次数超过一半的那个数。例如:5,6,5,89,5,56,5这7个数中,5出现的次数比其它数出现次数总和多1。在统计时,如果出现5就将出现次数加1,不出现5就将出现次数减1,会发现出现次数是这样变化的:1,0,1,0,1,0,1。用文字将这个过程表述一下就是:如果下一个数字与 5 相同,就将出现次数加1,否则就将出现次数减1。

更一般的描述是:如果下一个数字与前一个数字相同,就将出现次数加1,不同就将出现次数减1。改成这样时,不管事先是否知道5是出现次数最多的,统计到最后时,都会发现留有次数的是5。调换7个数字的顺序来验证这个一般性的想法,会发现这个想法是对的。将这个想法变成代码就得到了这题的最优解法了。

附带书中设计的函数:

Type Find(Type* ID, int N)
{
    Type candidate;
    int nTimes, i;
    for(i = nTimes = 0; i < N; i++)
    {
        if(nTimes == 0)
        {
             candidate = ID[i], nTimes = 1;
        }
        else
        {
            if(candidate == ID[i])
                nTimes++;
            else
                nTimes--;

        }

    }
    return candidate;
}

扩展问题

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

参考上面的解法,思路如下:

如果每次删除四个不同的ID(不管是否包含发帖数目超过总数1/4的ID),那么,在剩下的ID列表中,原先发帖比例大于1/4的ID所占比例仍然大于1/4。可以通过不断重复这个过程,把ID列表中的ID总数降低(转化为更小的问题),从而得到问题的答案。

void Find(Type* ID, int N,Type candidate[3])
{
    Type ID_NULL;//定义一个不存在的ID
    int nTimes[3], i;
    nTimes[0]=nTimes[1]=nTimes[2]=0;
    candidate[0]=candidate[1]=candidate[2]=ID_NULL;
    for(i = 0; i < N; i++)
    {
        if(ID[i]==candidate[0])
        {
             nTimes[0]++;
        }
        else if(ID[i]==candidate[1])
        {
             nTimes[1]++;
        }
        else if(ID[i]==candidate[2])
        {
             nTimes[2]++;
        }
        else if(nTimes[0]==0)
        {
             nTimes[0]=1;
             candidate[0]=ID[i];
        }
        else if(nTimes[1]==0)
        {
             nTimes[1]=1;
             candidate[1]=ID[i];
        }
        else if(nTimes[2]==0)
        {
             nTimes[2]=1;
             candidate[2]=ID[i];
        }
        else
        {
             nTimes[0]--;
             nTimes[1]--;
             nTimes[2]--;
         }
    }
    return;
}

延伸阅读

此文章所在专题列表如下:

  1. 编程之美2.3笔记:寻找发帖“水王”

本文地址:http://www.nowamagic.net/librarys/veda/detail/2377,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2377

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《链接器和加载器》 莱文(John R.Levine) (作者), 李勇 (译者)

《链接器和加载器》讲述构建程序的关键工具——链接器和加载器,内容包括链接和加载、体系结构、目标文件、存储分配、符号管理、库、重定位、加载和覆盖、共享库、动态链接和加载、动态链接的共享库,以及着眼于成熟的现代链接器所做的一些变化;并介绍一个持续的实践项目,即使用Perl语言开发一个可用的小链接器。《链接器和加载器》适合高校计算机相关专业的学生、实习程序员、语言设计者和开发人员阅读参考。

更多计算机宝库...