学步园

问题描述：”水王“发贴数超过所有帖子总数的一半，现有此论坛上所有帖子的列表，包含ID，如何快速找出这个水王？

解法一：对所有ID进行排序，再扫描一遍排好序的ID列表，统计各个ID出现的次数，如果某个IＤ出现的次数超过总数的一半，那么就输出这个ID。时间复杂度为O(N*log2N + N).

解法二：既然已经排好序，而且有某个ID出现的次数超过总数的一半，那么ID列表的中间项一定是这个ID。复杂度为O（1）。

解法三：如果每次删除两个不同的ID(不管是否包含"水王"的ID)，那么在剩下的ID列表中，"水王"的ID出现次数肯定仍然超过总数的一半。这样不断重复这个过程，总量就可以降低，从而避免了排序的操作，复杂度为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; 
}

后记：解法三体现了计算机科学中很普遍的思想：把一个问题转化为规模较小的若干个问题。算法里面的分治，递推与贪心等都是基于这样的思路。