面试任务:检查数组是否包含O(n)时间和O(1)附加内存中的对

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

需要提供一个函数实现,它检查参数数组是否只包含重复项,例如提供了两个数组:

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)存储空间

你怎么想,是否可能,因为我没有看到可能发生的方式......

不可能的结果比算法要困难得多,所以有一个像这样的明显无法解决的问题是令人沮丧的.

当然,没有一次通过算法,通过输入中点的通信复杂性参数.使用(例如)只有k个存储字,从第一个k + 1个项目中记住精确的多个集合是不可能的,因此我们可以使用另一个导致输出不正确的k + 1来跟踪这些项目.

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