arrays - 找到缺失的元素

Question

我看到了以下问题:

给定一个整数数组 A，找到 A 中不存在的整数 k。假设这些整数是 32 位有符号整数。

如何解决？

谢谢

////更新 - 这是提供的解决方案 - 但我认为它不正确//// 考虑一个非常简单的哈希函数 F(x)=x mod (n+1)。我们可以构建一个长度的位向量 n+1 初始化为 0，对于 A 中的每个元素，我们将位 F(A[i]) 设置为 1。由于数组中只有 n 个元素，因此我们可以轻松找到丢失的元素。

我认为上述解决方案是错误的。

例如， A [ 2, 100, 4 ]，那么 4 和 100 都会匹配到同一个位置。

Answer 1

如果我正确地解释了问题(找到 A 中不存在的任何整数)并且 n 是 A 中的元素数量，那么答案是正确的:给定。

哈希函数可能发生冲突这一事实并不重要；根据相反的鸽巢原理，位向量中会有某些位未被设置 - 因为它的位数比 A 中的元素多。对应的值是不在 A 中的整数。在哈希函数发生冲突的情况下，实际上会有不止一位未设置，这有利于算法的正确性，而不是不利。

为了说明这一点，您的示例的运行方式如下:

A = [2, 100, 4]
n = length(A) = 3
f(x) = x mod 4
map(f,A) = [2, 0, 0]

所以最终的位向量将是:

[1,0,1,0]

从那里，我们可以任意选择与任何 0 位相对应的任何整数，在本例中是任何奇数。