求解多数数问题。

问题描述：A[1..n]是n个整数，现要求找出多数数。多数数就是出现的次数大于[n/2]的数。例如1,2,3,3,3,3,4。由于3出现4次大于[7/2]，所以3是多数数。求一个复杂度O(n)的算法求出多数数。

解答：这个问题看似简单，因为O(n^2)复杂度的算法是很容易得到的，只需统计每个数出现的次数和[N/2]比较就可以了。但是现在要求O(n)复杂的算法就需要对问题更深入的理解了。

方法一：中位数法，一个序列的中位数就是将这个序列排序后，中间的那个数。比如说：3,1,2,4,5排序后就是1,2,3,4,5。那么中位数就是位于中间的3。那么中位数和多数数有什么关系呢？很简单，如果多数数存在的话，中位数一定就是多数数（这个自己去想为什么）。中位数通常是使用类似于Quick sort的方法来求解，平均复杂度O(nlgn)。但是有一种很复杂的经典方法是的中位数在O(n)可解。参考MIT的《算法导论》。
那么有些人可能要问了，万一多数数不存在怎么办呢？这个时候中位数就不是多数数了，因为多数数压根就不存在。但是这个问题很好解决!那就是对求出的中位数做一次check，看看他是不是多数数就可以了。check的过程是O(n)复杂度，所以总复杂度是O(n).

方法二：这种方法比较巧妙。我把它叫做多数数统计法。算法如下：
(1) num = A[1]; (假设多数数就是A[1])
(2) freq = 1; (多数数目前的出现次数为1)
(3) for(i = 2; i <= n; ++i)
{
if(A[i] == num)
++freq;
else
{
--freq;
if(freq == 0)
{
num = A[i];
freq = 1;
}
}
}

(4) 如果多数数存在，算法结束时，num就是多数数。若多数数不存在，如果你读了方法一，你应该知道怎么做了。

方法三：消去法。其实这种方法和方法二差不多，只是这种方法更容易读懂。
从A中寻找Ai，Aj使得Ai != Aj，此时将Ai和Aj从A中去除，不停得去掉A中的数，直到A中所有数都相等，则若多数数存在，该剩下的数是多数数。
简单证明一下:
设u表示多数数在A中出现的次数，v表示非多数数在A中出现的次数(v = n - u)。
那么上述从A中去除两个数的操作，使得对新的集合A'有两种情况：
对A'
(1)两个数都不是多数数，则v' = v - 2;
(2)两个数中有一个是多数数，则v'= v -1; u' = u - 1;
若多叔叔存在，u > v. 所以当消去操作无法进行的时候，即A中所有的数都相等的时候，v = 0, u>0因此A中剩下的数一定都是多数数了。

至此，该问题得到了圆满的解决，看完了别忘了点广告哦！