arrays - 采访任务: check if array consists of pairs in O(n) time and O(1) of additional memory

Question

这是我在面试中被问到的任务的一个例子，我认为它拼写错误或定义不当，但也许我错了，所以这里是:

需要提供一个函数的实现来检查参数数组是否仅包含重复项，例如提供了两个数组:

var x = [11,12,11,12]; // True, array consists of duplicates
var y = [66, 3278, 12, 12]; // False, 66 and 3278 contain no pair

问题在于算法应该在 O(n) 时间内执行此检查，内存空间为 O(1)

你怎么看，这可能吗，因为我看不到有可能发生的方式......

Answer 1

不可能的结果比算法更难得出，所以遇到这样一个明显无法解决的问题是令人沮丧的。

当然，通过输入中点的通信复杂性参数，没有一次性算法。对于(例如)只有 k 个存储字，从前 k+1 个项目中记住精确的多重集是不可能的，因此我们可以在这些项目之后加上另一个 k+1，这会导致不正确的输出。

另一方面，有一种概率算法在大多数情况下都能成功。计算应用于每个输入元素的伪随机函数的 XOR，当且仅当 XOR 为 0 时，返回元素配对。正如 Peter 在评论中观察到的那样，让伪随机函数成为恒等式是不够的，由于像 {0, 1, 2, 3} 这样的输入。 PRF 的要点是利用线性代数在 Z/2 上的特性，使得得到伪零的概率等于随机词为零的概率，对于长词来说，这个概率非常小.