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

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

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

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

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

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

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

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

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

原文地址:https://www.cnblogs.com/LeeZz/p/4499183.html