现在有一个数组，已知一个数出现的次数超过了一半，请用O(n)的复杂度的算法找出这个数。

分析：设数A出现次数超过一半。每次删除两个不同的数，在剩余的数中，数A出现的次数仍超过一半。通过重复这个过程，求出最后的结果。这个题目与编程之美中寻找水王相同

 

1 #include
     
       2 using namespace std;  3 //size为数组A的大小 4 //返回数组中出现超过一半的数 5 int search(int *A,int size) 6 { 7     int count=0; 8     int current; 9     for(int i=0;i
      
       >i;39     return 0;40 }41