查找重复次数超过 n/2 次的元素 [英] Find the element repeated more than n/2 times

问题描述

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

There is an array (of size N) with an element repeated more than N/2 number of time and the rest of the element in the array can also be repeated but only one element is repeated more than N/2 times. Find the number.

我能想到几种方法:

• 天真，在哈希图中保留每个数字的计数.
• 最简单，对数组进行排序，第 n/2+1 个索引处的数字是需要的号码.
• 仅对找到的连续重复值进行计数.查看分别用于交替存储值的模式.

无法想到更好的解决方案，必须有.

Unable to think of a better solution, there has to be.

推荐答案

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

There is a beautiful algorithm for solving this that works in two passes (total time O(N)) using only constant external space (O(1)). I have an implementation of this algorithm, along with comments including a correctness proof, available here

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

The intuition behind the algorithm is actually quite beautiful. Suppose that you were to have a roomful of people each holding one element of the array. Whenever two people find each other where neither is holding the same array element as the other, the two of them sit down. Eventually, at the very end, if anyone is left standing, there's a chance that they're in the majority, and you can just check that element. As long as one element occurs with frequency at least N/2, you can guarantee that this approach will always find the majority element.

要实际实现该算法，您需要对数组进行线性扫描，并跟踪您当前对多数元素是什么的猜测，以及到目前为止您看到它的次数.最初，这个猜测是未定义的，重复次数为零.当您遍历数组时，如果当前元素与您的猜测相符，则增加计数器.如果当前元素与您的猜测不符，您将递减计数器.如果计数器达到零，那么您将其重置为您遇到的下一个元素.您可以将此实现视为上述站在房间里"算法的具体实现.每当两个人遇到不同的元素时，他们就会取消(放下计数器).每当两个人有相同的元素时，他们就不会相互交互.

To actually implement the algorithm, you make a linear scan over the array and keep track of your current guess as to what the majority element is, along with the number of times that you've seen it so far. Initially, this guess is undefined and the number of repeats is zero. As you walk across the array, if the current element matches your guess, you increment the counter. If the current element doesn't match your guess, you decrement the counter. If the counter ever hits zero, then you reset it to the next element you encounter. You can think about this implementation as a concrete realization of the above "standing around in a room" algorithm. Whenever two people meet with different elements, they cancel out (dropping the counter). Whenever two people have the same element, then they don't interact with each other.

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

For a full correctness proof, citation to the original paper (by Boyer and Moore of the more famous Boyer-Moore string matching algorithm), and an implementation in C++, check out the above link.

这篇关于查找重复次数超过 n/2 次的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！