arrays - 查找重复超过 n/2 次的元素

Question

有一个数组(大小为 N)，其中一个元素重复了 N/2 次以上，数组中的其余元素也可以重复，但只有一个元素重复大于 N/2 次。找到号码。

我能想到几种方法:

• 天真，将每个数字的计数保存在 HashMap 中。
• 最简单，对数组进行排序，第n/2+1个索引处的数为所需数量。
• 只记录找到的连续重复值。查看分别用于交替存储值的模式。

想不出更好的解决方案，只能有。

Answer 1

有一个漂亮的算法可以解决这个问题，它只使用恒定的外部空间 (O(1)) 分两次通过(总时间 O(N))。我有这个算法的实现，以及包括正确性证明在内的评论， available here

算法背后的直觉其实很漂亮。假设你有一屋子人，每人拿着数组的一个元素。每当两个人发现对方没有持有与对方相同的阵元时，两人就坐下。最终，在最后，如果有人留下来，那么他们有可能占多数，你可以检查那个元素。只要一个元素出现的频率至少为 N/2，就可以保证这种方法总能找到多数元素。

要实际实现该算法，您需要对数组进行线性扫描，并跟踪您当前对多数元素是什么的猜测，以及您到目前为止看到它的次数。最初，这个猜测是不确定的，重复次数为零。当您遍历数组时，如果当前元素与您的猜测相符，则递增计数器。如果当前元素与您的猜测不符，则递减计数器。如果计数器达到零，则将其重置为遇到的下一个元素。您可以将此实现视为上述“standing around in a room”算法的具体实现。每当两个人遇到不同的元素时，他们就会抵消(丢弃计数器)。每当两个人具有相同的元素时，他们就不会相互交互。

有关完整的正确性证明、对原始论文的引用(由 Boyer 和 Moore 撰写的更著名的 Boyer-Moore 字符串匹配算法)以及 C++ 实现，请查看上面的链接。