查找重复超过n / 2次的元素
存在一个数组（大小为N），其中元素重复的次数超过N / 2次，并且 的
但是只有一个元素重复的次数超过N / 2次。查找号码。
我可以想到几种方法：
- 天真，将每个数字的计数保留在哈希图中。
- 最简单的方法是对数组排序，第n / 2 + 1个索引处的数字是所需的数字。
- 保留仅找到的连续重复值的计数。分别检查是否交替存储值的模式。
必须想到一个更好的解决方案。
回答：
有一个漂亮的算法可以解决此问题，该算法仅使用恒定的外部空间（O（1））就可以进行两次遍历（总时间O（N））。我有此算法的实现，以及包含正确性证明的注释，
该算法背后的直觉实际上很漂亮。假设您要有一群人，每个人都拿着数组的一个元素。每当两个人发现彼此都不持有相同数组元素的地方时，他们两个就坐下。最终，如果最后有人站着，他们很有可能占多数，您可以检查一下该元素。只要一个元素出现的频率至少为N
/ 2，就可以保证此方法将始终找到多数元素。
为了真正实现该算法，您需要对数组进行线性扫描，并跟踪当前对多数元素是什么的猜测以及迄今为止看到它的次数。最初，这种猜测是不确定的，重复次数为零。当您遍历数组时，如果当前元素与您的猜测相符，则可以增加计数器。如果当前元素与您的猜测不符，则将计数器递减。如果计数器达到零，则将其重置为遇到的下一个元素。您可以将此实现视为上述“在房间里站立”算法的具体实现。每当两个人遇到不同元素时，他们就会抵消（丢弃计数器）。每当两个人具有相同的元素时，他们就不会彼此互动。
为了获得完全的正确性证明，请引用原始文章（更著名的Boyer-Moore字符串匹配算法的Boyer和Moore）以及C ++中的实现，请查看上面的链接。
以上是 查找重复超过n / 2次的元素 的全部内容， 来源链接： utcz.com/qa/418381.html
