题目：给定一个由n-1个整数组成的未排序的数组序列，其元素都是1到n中的不同整数。请写出一个寻找数组序列中缺失整数的线性时间算法。

分析：异或法。异或运算，当参与运算的两个数相同时，结果为假，当两个数不同，则结果为真。

a = 1 ^ 2 ^ 3 ^ ...^ n。b = 1 ^ 2 ^ 3^...(m-1) ^ (m+1) ^ ...^n，其中m表示缺失数字。所以a ^  b = (1 ^ 1)^(2 ^ 2)...(m-1) ^(m-1)^m^(m+1)^(m+1)...^(n^n) = m。

code:

def getNum(arr):

    if arr is None or len(arr) <= 0:

        return -1

    a = arr[0]

    i = 1

    while i < len(arr):

        a ^= arr[i]

        i += 1

    b = 1

    i = 2

    while i <= len(arr) + 1:

        b ^= i

        i += 1

    return a ^ b

if __name__ == "__main__":

    arr = [1, 4, 3, 2, 7, 5]

    print(getNum(arr))

程序运行结果为：

6