寻找发帖水王

最 近,零零散散的看了《编程之美》这本书的一两道题,发现都是挺有趣的题目,书里面的 思路很好，看完后启发真不少，其中有一道叫“寻找发帖水王”的题目，用一般思路去解决，时间复杂度会是O（N * log₂N + N）。但换一种简单的思路却可以是O（N），这对程序来说，在运行效率上应该是质的飞跃了。

原题目如下：.

为了方便说明，贴出题目伪代码如 下：

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;

}

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吗？

这道题显然还是用原题中的思路去解决，但问题复杂了，由原来的一个水王，变成了3个， 且他们的总数目皆超过总体数的1/4。我的思路如下：

    首先，上题思路是，当遍历ID与当前ID（candidate变量）不同时，当前ID（candidate变量）所遍历到的个数减1（nTimes - 1）,相同则遍历数加1，当nTimes等于0时，就说明，当前ID遍历到的个数为0或已被抵消为0，那当前ID就等于新遍历到的ID，且其遍历数赋为 1（当然这个新遍历到的ID可以等于当前），这就意味着，整个遍历下来，相同的ID都会被累加起来，而不同ID之间会互相抵消，最后剩下来的 candidate变量就是灌水王ID，但我们能保证一定是灌水王的ID吗？让我们假设一种最极端的状况就是，所有非灌水王ID都与灌水王ID抵消，但因 为，灌水王占大于总帖数一半的帖数，故其总遍历数减去所有帖子数，总会大于0，所以最终返回的condidate变量总会是灌水王的ID。

   有了上题的思路之后，我们就着手于这一题了。上题只需要一个结果，而现在需要3个结果，所以我们考虑数组作为返回值，同时，上题用到的nTimes，也应 改为一个大小为3的数组。我们要如何保证最终返回的数组的3个元素就是3个灌水最多的用户呢？首先分析其所占比例，各超过1/4,也就是说剩下的其它ID 所占帖数就不足总帖数1/4了。现在我们需要3个变量来记录当前遍历过的3个不同的ID，而nTimes的3个元素分别对应当前遍历过的3个ID出现的个 数。如果遍历中有某个ID不同于这3个当前ID，我们就判断当前3个ID是否有某个的nTimes为0，如果有，那这个新遍历的ID就取而代之，并赋1为 它的遍历数（即nTimes减1），如果当前3个ID的nTimes皆不为0，则3个ID的nTimes皆减去1，这也就是解决本文题的关键了。由于非水 王ID不满总帖数的1/4,与上题思路相同，所遍历ID与当前3个ID不同时，就一同抵消（即3个当前ID的nTimes值减1），最终留下来的3个当前 ID总会是3个超过1/4的水王ID。

 

具体算法伪代码如下：（写的比较复杂，没有做代码优化）

   1. Type * find(Type * ID,int n){ 
   2.   /*
   3.     n       帖子总数，
   4.     ID      用户ID列表
   5.     result  储存3个当前遍历到的不同ID
   6.     nTimes  储存对应ID已遍历到的个数被抵消后的值
   7.   */ 
   8.   Type result[] = {NULL,NULL,NULL}; 
   9.  
  10.   int i; 
  11.  
  12.   int nTimes[] = {0,0,0}; 
  13.  
  14.   for(i=0;i  15.  
  16.    if(nTimes[0] == 0 && ID[i] != result[1] && ID[i] != result[2]){ 
  17.  
  18.       nTimes[0] = 1; 
  19.  
  20.       result[0] = ID[i]; 
  21.  
  22.     } 
  23.  
  24.     else if(nTimes[1] == 0 && ID[i] != result[0] && ID[i] != result[2]){ 
  25.  
  26.          nTimes[1] = 1; 
  27.  
  28.          result[1] = ID[i]; 
  29.  
  30.   
  31.  
  32.     } 
  33.  
  34.      else if(nTimes[2] == 0 && ID[i] != result[0] && ID[i] != result[1]){ 
  35.  
  36.          nTimes[2] = 1; 
  37.  
  38.          result[2] = ID[i]; 
  39.  
  40.   
  41.  
  42.      } 
  43.  
  44.      else if(ID[i] != result[0] && ID[i] != result[1] && ID[i] != result[2] ){ 
  45.  
  46.        nTimes[0] -= 1; 
  47.  
  48.        nTimes[1] -= 1; 
  49.  
  50.        nTimes[2] -= 1; 
  51.  
  52.      }else if(ID[i] == result[0]){ 
  53.  
  54.          nTimes[0] += 1; 
  55.  
  56.      }else if(ID[i] == result[1]){ 
  57.  
  58.          nTimes[1] += 1; 
  59.  
  60.      }else if(ID[i] == result[2]){ 
  61.  
  62.          nTimes[2] += 1; 
  63.  
  64.      } 
  65.  
  66.   
  67.  
  68.   } 
  69.  
  70. return result; 
  71.  
  72.  }