如何在一堆数字中快速找到出现次数最多的一个？

Question

一堆数字里有一个数占了整堆数字的一半以上，另外的数字都是随机的，如何快速找到这个出现最多的数字？

Answer 1

楼上的方法不能说不对，不过 ， 这个问题是有经典算法的：
先举个例子吧：

2 3 4 4 5 5 4 4 4

上面这个数列 ， 4 明显是要找的数 。 因为4的个数占了整堆数字的一半以上 ， 所以我们可以把数列分为下面几对：

2 4
3 4
5 4
5 4
4

这样每对都有一个4 ， 最后还剩下4 ， 说明 4 就是我们要找的数 ，算法的思想就是，不停的消去数字对 ， 最后剩下的数 ， 就是要找的数字。
所以算法的伪代码如下：

 (1)计数器count置1，另c=A[1];
 (2)从A[2]开始向后扫描，for j=2 to n
             若a[j]与c相等，则count++;
             若a[j]与c不等，则count—
             若count==0,则对A[j+1...n]寻找多数元素候选者。
             
             
 int Candidate(int A[],int m ,int n)  
    {//寻找A[m...n]中多数元素候选者
     c=A[m];count=1;
     for(j=m+1;j<n&&count>0)
     {
        if(A[j]==c)
            count++
        else count--;
        }
        if(j==n)return  c;
        else return canditate(A, j+1 , n); //对则对A[j+1...n]寻找多数元素候 选者。
     }

具体的参考： 《算法设计技巧与分析》 p98

Answer 2

编程之美的题目...百度面试还问过...

Answer 3

数据量大的话用分治法：最小分割单位为3，不过这样会有些误差，呵呵
数据量小的话用hash法