下面是我的面试问题之一。鉴于N个元素的数组，并在一个元素出现的正是N / 2 倍，其余N / 2个元素是唯一。你会如何​​找到该元素具有更好的运行时间？

Here is one of my interview question. Given an array of N elements and where an element appears exactly N/2 times and the rest N/2 elements are unique. How would you find the element with a better run time?

记住的元素是不能排序，你可以假设N是偶数。例如，

Remember the elements are not sorted and you can assume N is even. For example,

input array [] = { 10, 2, 3, 10, 1, 4, 10, 5, 10, 10 }

因此​​，这里10出现准确传达5倍，它是N / 2。

So here 10 appears extactly 5 times which is N/2.

我知道有O（n）的运行时间的解决方案。不过还是期待知道有O（log n）的一个更好的解决方案。

I know a solution with O(n) run time. But still looking forward to know a better solution with O(log n).

推荐答案

有一个固定的时间的解决方案，如果你愿意接受错误的概率很小。从数组中随机采样两个值，如果它们是相同的，你找到你要找的价值。在每个步骤中，你有没有完成的0.75概率。而且，由于对每一个ε，存在一个n使得（3/4）^ N＆LT; EPS，我们可以在最n次采样，如果我们没有找到匹配的一对返回一个错误。

There is a constant time solution if you are ready to accept a small probability of error. Randomly samples two values from the array, if they are the same, you found the value you were looking for. At each step, you have a 0.75 probability of not finishing. And because for every epsilon, there exists one n such that (3/4)^n < eps, we can sample at most n time and return an error if we did not found a matching pair.

此外此话的是，如果我们继续取样，直到找到一对，预期的运行时间是恒定的，但运行时间的最坏的情况是无界

Also remark that, if we keep sampling until we found a pair, the expected running time is constant, but the worst case running time is not bounded.