有一个漂亮的算法可以解决此问题，该算法仅使用恒定的外部空间（O（1））就可以进行两次遍历（总时间O（N））。我有此算法的实现，以及包含正确性证明的注释，
可在此处获得

该算法背后的直觉实际上很漂亮。假设您要有一群人，每个人都拿着数组的一个元素。每当两个人发现彼此都不持有相同数组元素的地方时，他们两个就坐下。最终，如果最后有人站着，他们很有可能占多数，您可以检查一下该元素。只要一个元素出现的频率至少为N
/ 2，就可以保证此方法将始终找到多数元素。

为了真正实现该算法，您需要对数组进行线性扫描，并跟踪当前对多数元素是什么的猜测以及迄今为止看到它的次数。最初，这种猜测是不确定的，重复次数为零。当您遍历数组时，如果当前元素与您的猜测相符，则可以增加计数器。如果当前元素与您的猜测不符，则将计数器递减。如果计数器达到零，则将其重置为遇到的下一个元素。您可以将此实现视为上述“在房间里站立”算法的具体实现。每当两个人遇到不同元素时，他们就会抵消（丢弃计数器）。每当两个人具有相同的元素时，他们就不会彼此互动。

为了获得完全的正确性证明，请引用原始文章（更著名的Boyer-Moore字符串匹配算法的Boyer和Moore）以及C ++中的实现，请查看上面的链接。