寻找发帖水王（编程之美）

这是编程之美上的一道题目，大意是说：给n个数，其中有一个数出现的次数超过了一半，如何求出这个数。

 

这个题目一般的做法是先进行排序，然后统计数字出现的次数。这样的复杂度是O（nlogn)（貌似我刚开始也只能想出这样的算法...).然后书上提出一个稍微改进的方法，就是说排序后中间的那个数必然是出现次数超过一半的数（这不需要证明吧）。不过即使是这样，复杂度仍然是O(nlogn).

 

完美的解法是：如果每次删掉两个不同的数，那么在剩下的数中，那个数出现的次数仍然超过一半，这样重复下去，最后就可以求出这个数。这样总的复杂度就是O(n)，并且只需要常数的内存（这是优于hash法的地方）。在实现的时候需要注意并不需要实际的去删除数。代码如下：

 

#include<iostream>
using namespace std;
int find(int *id,int N)
{
     int 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;
}
int main()
{
     int n;
     cin>>n;
     int num[100];
     for(int i=0;i<n;i++)
     cin>>num[i];
     int value=find(num,n);
     cout<<value<<endl;
     for(;;);
     return 0;
}