arrays - 找出恰好出现 N/2 次的数字

Question

这是我的面试问题之一。给定一个包含 N 个元素的数组，其中一个元素出现恰好 N/2 次，其余 N/2 个元素唯一。您将如何找到具有更好运行时间的元素？

记住元素没有排序，你可以假设 N 是偶数。例如，

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

所以这里 10 正好出现 5 次，即 N/2。

我知道一个运行时间为 O(n) 的解决方案。但仍然期待知道 O(log n) 的更好解决方案。

Answer 1

如果您愿意接受很小的错误概率，那么就有一个恒定时间的解决方案。从数组中随机抽取两个值，如果它们相同，则找到了要查找的值。在每一步，您有 0.75 的概率没有完成。并且因为对于每个 epsilon，存在一个 n 使得 (3/4)^n < eps，我们最多可以采样 n 次，如果我们没有找到匹配对则返回错误。

另请注意，如果我们一直采样直到找到一对，则预期运行时间是常数，但最坏情况下的运行时间不受限制。