我有一个问题  例如，我们有数组

i have one problem for example we have array

int a[]=new int[]{a1,a2,a3,a4,..........an}:

任务是这是不数组中的元素填充同一阵列 例如 A = {1,3,4,5,6,7} 应该由任何数字填写 {2,8,9,12,13 90} 或其他人而不是由它们在数组中的元素，不可{ 1,12,13,14,110} ，因为1是在所述阵列的 谢谢

task is fill the same array by elements which are not in the array for example a={1,3,4,5,6,7} should be filled by any numbers {2,8,9,12,13,90}or others but not by elements which are in array this must not be{1,12,13,14,110} because 1 is in the array a thanks

推荐答案

有趣的问题。

如果数组是有符号整数，我相信这是可能在O（n）时间及O（1）空间，无溢出，假设其长度足够小，以允许这样的事情发生。

If the array is of signed integers, I believe it is possible in O(n) time and O(1) space, with no overflows, assuming the length is small enough to permit such a thing to happen.

的基本思想是：

我们有n个数。现在，由N + 1除以这些数字，我们得到n个余。因此剩余部分的在用于至少一个{0,1,2，...，n}的必须失去（说r）的。我们充满数字的余数为R阵列。

We have n numbers. Now on dividing those numbers by n+1, we get n remainders. So atleast one of the remainders in {0,1,2, ..., n} must be missing (say r). We fill the array with numbers whose remainders are r.

首先，我们添加了N + 1的倍数，以所有负数，使他们积极的。

First, we add a multiple of n+1 to all negative numbers to make them positive.

接下来我们走的阵列，并找到每个数N + 1的剩余部分。如果余数为r，我们制定了一个[R]是-a [R]如果[R]为阳性。 （如果我们走的时候遇到负数，我们取余数时，使用否定版本）。

Next we walk the array and find the remainder of each number with n+1. If remainder is r, we set a[r] to be -a[r] if a[r] was positive. (If we encounter negative numbers when walking, we use the negated version when taking remainder).

我们也有一个额外的int的剩余= N

We also have an extra int for remainder = n.

最后，我们再次走阵列，看看是否有任何正数（会有的，或额外的int的剩余= n将被取消设置）。

At the end, we walk the array again to see if there are any positive numbers (there will be one, or the extra int for remainder = n will be unset).

在我们的其余部分，很容易产生与其余n个数。当然，我们总是可以生成一个号码，并与填充它，因为这个问题从来没有说过唯一编号事情。

Once we have the remainder, it is easy to generate n numbers with that remainder. Of course we could always generate just one number and fill it with that, as the problem never said anything about unique numbers.

如果该阵列是无符号整数的，我们可以的也许的仍具有较好的簿记做到这一点。

If the array was of unsigned integers, we could probably still do this with better book-keeping.

例如，我们可以尝试使用前n / LOGN整数作为我们bitarray表示其馀已经见过并使用一些额外的O（1）整数临时保存的数字。

For instance we could try using the first n/logn integers as our bitarray to denote which remainders have been seen and use some extra O(1) integers to hold the numbers temporarily.

有关，例如，你做的TMP =的[0]，发现剩下的时间和设置相应位A [0]（其设置为零第一后）。 TMP = A [1]中，设置位等。我们绝不会覆盖一个数字之前，我们需要它来找到它的其余部分。

For eg, you do tmp = a[0], find remainder and set the appropriate bit of a[0] (after setting it to zero first). tmp = a[1], set bit etc. We will never overwrite a number before we need it to find its remainder.