八、 算法题：有一个长度为n一1的数组，包含1一n中不重复的乱序的数，求寻找范围内不在数组中的数，考虑空间占用，性能优化，溢出等情况，至少写两个算法

Answer 1

当n不太大时，可以考虑求和。先算出1~n的所有数的和，然后减去数组中出现的所有自然数的和。时间复杂度为O(n)，空间复杂度O(1)。这种方法的缺点是n不能太大，n比较大时，求和容易溢出。 用位图。从头到尾的扫描整个数组，把出现的数相应的位设置为1.然后再扫描位图，找出不为1的那一位，即为要找的数。这种方法的时间复杂度为O(n),空间复杂度为O(n)。 异或有个很巧妙的地方：同一变量和该变量与另一变量的异或值的异或等于这个变量自身。所以我们可以把1~n的所有数异或，再把数组中出现的所有数异或，然后再把这两个异或的结果异或，最后得到的值即为我们要找的值。这样时间复杂度为O(n),空间复杂度为O（1）。在空间上比第二种方法要好，而且不会出现第一种方法中所说的溢出问题。