经典面试题-数组中出现次数超过一半的数

【题意】：数组中有一个数字出现超过半数以上，找出这个数字。

【解析】：一个数字超过半数以上，这是本题仅有的条件，所以，我们要从这个条件入手。

数字超过半数有什么特性呢？首先这个数字肯定是这些数的中位数。所以可以排序，然后找中位数。

但是时间复杂度为排序的O(n*logn)，还可以再快吗？

现在有这么一个思路，我们知道，要求的这个数超过半数，那么两个不同的数我们消除，相同的累加，

最后一定能剩下那个超过半数的数字。

具体操作：用一个变量用来存当前剩下的数字，用一个变量做计数器。每次比较数字是否相同，相同累加

不同相消，计数器为0时，换数字。

原文：http://www.cnblogs.com/LeeZz/p/4499183.html