问题描述
有（大小为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个索引是规定的数量。
- 在保持发现，只有连续的重复值计数。检查分别为，其中的值是交替存储的模式。
- Naive, keep the count of each number in a hash map.
- Simplest, sort the array and the number at n/2+1 th index is therequired number.
- Keep count of only consecutive duplicate values found. Checkseparately for the pattern where the values are stored alternatively.
无法想到更好的解决方案，必须有。
Unable to think of a better solution, there has to be.
推荐答案
有一个美丽的算法求解这一点，工作在两个通道（总时间为O（N））使用唯一不变的外部空间（O（1））。我有这个算法的实现，以及意见，包括正确性证明， 可以在这里找到
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.
有关完整的正确性证明，引用到原来的纸（博耶和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次的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！