我看到了以下问题：

由于整数数组A，找到一个整数k不是present A中假设的整数是32位有符号整数。

Given an array A of integers, find an integer k that is not present in A. Assume that the integers are 32-bit signed integers.

如何解决呢？

感谢您

////更新 - 这是所提供的解决方案 - 但我不认为这是正确的//// 考虑一个非常简单的哈希函数F（x）= X模（N + 1）。我们可以建立长度的位向量 N + 1被初始化为0，对于在每一个元素，我们设置位F（A [1]），以1.Since只有n个数组中的元素，我们可以很容易地找到缺少的元素。

//// update -- This is the provided solution - but I don't think it is correct //// Consider a very simple hash function F(x)=x mod (n+1). we can build a bit-vector of length n+1 that is initialized to 0 and for every element in A, we set bit F(A[i]) to 1.Since there are only n elements in the array, we can find the missing element easily.

我觉得上面的解决方案是错误的。

I think the above solution is wrong.

例如， A [2，100，4]，那么这两个4和100将匹配了同一个地方。

For example, A [ 2, 100, 4 ], then both 4 and 100 will match to the same place.

推荐答案

如果我是跨$ P $正确pting的问题，（找到的任意的整数不在A）和 N 为A类元素的数量，那么答案是正确的，因为给定的。

If I'm interpreting the question correctly, (find any integer not in A) and n is the number of elements in A, then the answer is correct as given.

这是哈希函数可以有冲突的事实其实并不重要;通过以相反的鸽巢原理，会出现的一些的在未设置该位向量位 - 因为其具有更多的位之外还有在A中的元素的相应值是一个整数不是A.在散列函数具有冲突的情况下，实际上将一个以上的位未设置，有利于该算法的正确性的其中工程而不是人。

The fact that the hash function can have collisions doesn't really matter; By the pigeonhole principle in reverse, there will be some bit in the bit vector that is not set - because it has more bits than there are elements in A. The corresponding value is an integer not in A. In the case where the hash function has collisions, there will actually be more than one bit not set, which works in favor of the algorithm's correctness rather than against it.

要说明这一点，这里是如何的例子就是制定出：

To illustrate, here's how your example would work out:

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

因此​​最终位向量将是：

so the final bit vector will be:

[1,0,1,0]

从那里，我们可以任意地选择对应于任何位0，而在这种情况下，是任何奇数任何整数。

From there, we can arbitrarily choose any integer corresponding to any 0 bit, which in this case is any odd number.