【出自WR面试题】
难度系数：★★★★☆ 被考察系数：★★★☆☆
题目描述：
给定一个由n-1个整数组成的未排序的数组序列，其元素都是1到n中的不同的整数。请写出一个寻找数组序列中缺失整数的线性时间算法。
分析与解答：
方法一：累加求和
首先分析一下数学性质。假设缺失的数字是X，那么这n-1个数一定是1～n之间除了X以外的所有数，试想一下，1～n一共n个数的和是可以求出来的，数组中的元素的和也是可以求出来的，二者相减，其值是不是就是缺失的数字X的值呢？
为了更好地说明上述方法，举一个简单的例子。假设数组序列为{2，1，4，5}一共4个元素，n的值为5，要想找出这个缺失的数字，可以首先对1～5这五个数字求和，求和结果为15（1+2+3+4+5=15），而数组元素的和为array[0]+array[1]+array[2]+array[3]=2+1+4+5=12，所以，缺失的数字为15-12=3。
通过上面的例子可以很容易形成以下具体思路：定义两个数suma与sumb，其中，suma表示的是这n-1个数的和，sumb表示的是这n个数的和，很显然，缺失的数字的值即为sumb-suma的值。
示例代码如下：
程序的运行结果如下：(www.xing528.com)
6
算法性能分析：
这种方法的时间复杂度为O（N）。需要注意的是，在求和的过程中，计算结果有溢出的可能性。所以，为了避免这种情况的发生，在进行数学运算时，可以考虑位运算，毕竟位运算性能最好，下面介绍如何用位运算来解决这个问题。
方法二：异或法
在解决这个问题前，首先回顾一下异或运算的性质。简单点说，在进行异或运算时，当参与运算的两个数相同时，异或结果为假，当参与异或运算的两个数不相同时，异或结果为真。
1～n这n个数异或的结果为a=1^2^3^…^n。假设数组中缺失的数为m，那么数组中这n-1个数异或的结果为b=1^2^3^…（m-1）^（m+1）^…^n。由此可知，a^b=（1^1）^（2^2）^…（m-1）^（m-1）^m^（m+1）^（m+1）^…^（n^n）=m。根据这个公式可以得知本题的主要思路是：定义两个数a与b，其中，a表示的是1～n这n个数的异或运算结果，b表示的是数组中的n-1个数的异或运算结果，缺失的数字的值即为a^b的值。
实现代码如下：
算法性能分析：
这种方法在计算结果a的时候对数组进行了一次遍历，时间复杂度为O（N），接着在计算b的时候循环执行的次数为N，时间复杂度也为O（N）。因此，这种方法的时间复杂度为O（N）。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
