document.write('方法一：累加求和
首先分析一下数学性质。假设缺失的数字是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的值。
示例代码如下：
def getNum(arr):
if arr==None or len(arr)＜=0:
print "参数不合理"
return -1
suma=0
sumb=0
i=0
while i＜len(arr):
suma=suma+arr[i]
sumb=sumb+i
i+=1
sumb=sumb+len(arr)+len(arr)+1
return sumb-suma
if __name__=="__main__":
arr=[1,4,3,2,7,5]
print getNum(arr)
程序的运行结果为：
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)^(m1)^m^(m+1)^(m+1)^…^(n^n)=m。根据这个公式可以得知本题的主要思路为：定义两个数a与b，
其中，a表示的是1到n这n个数的异或运算结果，b表示的是数组中的n-1个数的异或运算结果，缺失的
数字的值即为a^b的值。
实现代码如下：
def getNum(arr):
if arr==None or len(arr)＜=0:
print "参数不合理"
return -1
a=arr[0]
b=1
lens=len(arr)
i=1
while i＜lens:
a=a^arr[i]
i+=1
i=2
while i＜=lens+1:
b=b^i
i+=1
return a^b
if __name__="__main__":
arr=[1, 4, 3, 2, 7, 5]
print getNum(arr)
算法性能分析：
这种方法在计算结果a的时候对数组进行了一次遍历，时间复杂度为O(N)，接着在计算b的时候循环
执行的次数为N，时间复杂度也为O(N)。因此，这种方法的时间复杂度为O(N)。
');