題目：給定一個(gè)由n-1個(gè)整數(shù)組成的未排序的數(shù)組序列光绕，其元素都是1到n中的不同整數(shù)。請(qǐng)寫出一個(gè)尋找數(shù)組序列中缺失整數(shù)的線性時(shí)間算法畜份。
分析：異或法诞帐。異或運(yùn)算，當(dāng)參與運(yùn)算的兩個(gè)數(shù)相同時(shí)爆雹，結(jié)果為假停蕉，當(dāng)兩個(gè)數(shù)不同愕鼓，則結(jié)果為真。
a = 1 ^ 2 ^ 3 ^ ...^ n慧起。b = 1 ^ 2 ^ 3^...(m-1) ^ (m+1) ^ ...^n菇晃，其中m表示缺失數(shù)字。所以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))
程序運(yùn)行結(jié)果為：
6
