题目描述(简单难度)

给一个数组，存在一个数字超过了半数，找出这个数。

解法一

这种计数问题，直接就会想到，遍历过程中统计每个数字出现的个数即可。可以确定的是，超过半数的数字一定有且只有一个。所以在计数过程中如果出现了超过半数的数字，我们可以立刻返回。

上边的解法时间复杂度是 O(n)，同时也需要 O(n) 的空间复杂度。所以下边讨论在保证时间复杂度不变的情况下，空间复杂度为 O(1) 的解法。

看到介绍的。

137 题解法三中已经用过这个思想了，就是把数字放眼到二进制的形式，举个例子。

由于 2 是超过半数的数，它的二进制是 010，所以对于从右边数第一列一定是 0 超过半数，从右边数第二列一定是超过半数，从右边数第三列一定是 0 超过半数。然后每一列超过半数的 0,1,0 用 10进制表示就是 2 。

当然，我们可以只统计的个数，让每一位开始默认为 0，如果发现某一列的 1 的个数超过半数，就将当前位改为 1。

具体算法通过按位与和按位或实现。

1980 年由 Boyer 和 Moore 两个人提出来的算法，英文是。

算法思想很简单，但第一个想出来的人是真的强。

我们假设这样一个场景，在一个游戏中，分了若干个队伍，有一个队伍的人数超过了半数。所有人的战力都相同，不同队伍的两个人遇到就是同归于尽，同一个队伍的人遇到当然互不伤害。

这样经过充分时间的游戏后，最后的结果是确定的，一定是超过半数的那个队伍留在了最后。

group 记录当前队伍的人数，count 记录当前队伍剩余的人数。如果当前队伍剩余人数为 0，记录下次遇到的人的所在队伍号。

解法一用计数的方法经常用到，很容易想到。解法二把数字放眼到二进制的世界，也算是经常用到了。解法三只能说 666 了，太强了，神仙操作。

添加好友一起进步~

如果觉得有帮助的话，可以点击这里给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击查看详情