查找数组出现次数超过一半的数

首页 > 技术文章 > 查找数组出现次数超过一半的数

cyf333333 2016-05-22 17:06 原文

三种思路：

最基本的：

排序，然后遍历

打擂法：该方法适用于某个数出现的次数超过半数的情况

从第一个数开始，上擂台
后一个数如果与擂台上的一致，则守擂计数+1
后一个数如果与擂台上的不一致，则守擂计数-1
一旦守擂计数减为0，就将台上的数挤掉，然后刚刚打擂的数上台

类似上一种：

任意两个不同的数相互抵消，最后剩下的唯一个或多个相同的数就是最多的数

一旦找出最多的数，就可以重新遍历得到该数的出现次数了

1
2

推荐阅读