? ? ?在一個無序數組里有99個不重復的正整數，范圍是1~100，唯獨缺少1個1~100中的整數。如何找出這個缺失的整數?

? ? ? 一個很簡單也很高效的方法，先算出1~100之和，然后依次減去數組里的元素，最后得到的差值，就是那個缺失的整數。

假設數組長度是n，那么該解法的時間復雜度是O (n)，空間復雜度是O (1)。

import random
#數組
def find_1(n):ll=[]#隨機生成1-n的一個數作為缺失數rd= random.randint(1,n+1)# print(rd)#循環數據for i in range(1,n+1):if i!=rd:ll.append(i)print(ll)return ll#查找缺失的整數
def find_number(n):ll=find_1(n)#累計和sum1=sum(ll)#累計1..n和sum2=((1+n)*n)//2print(sum1,sum2)return sum2-sum1if __name__ == '__main__':# print(find_number(10))print(find_number(100))

?

擴展題1：

一個無序數組里有若干個正整數，范圍是1~100，其中99個整數都出現了偶數次，只有1個整數出現了奇數次，如何找到這個出現奇數次的整數?

? ? ?遍歷整個數組，依次做異或運算。由于異或運算在進行運算時，相同為0，不同為1，

? ? ?因此所有出現偶次的整數都會相互抵消成為0，只有唯一出現奇數的整數會被留下。

?

def find2(ll):lost=0for i in range(len(ll)):#異或運算lost=lost^ll[i]return lostif __name__ == '__main__':ll=[3,1,3,2,2,8,1]print(find2(ll))

如果數組長度為n，該解法的時間復雜度是O(n)，空間復雜度為O(1)。?

?擴展題2：

假設一個無序數組里有若干個正整數， 范圍是1～ 100， 其中有98個整數出現了偶數次， 只有2個整數出現了奇數次， 如何找到這2個出現奇數次的整數？

使用分治算法,設這兩個整數為A，B。

1、先將數組內元素異或得到A，B的異或值。

2、將該值對應的二進制位從右至左找到第一個為1的值sep，表示A，B對應的二進制表示在此處的位置相異，設A為1，B為0。

3、利用此區別，將數組中的其他元素和sep相與，為1和A劃為一組，為0和B劃為一組。

4、利用擴展1求解。

def find3(ll):# 用于存儲兩個出現奇數次的整數result=[0,0]# 第一次整體異或lost = 0for i in range(len(ll)):# 異或運算lost = lost ^ ll[i]# 如果異或結果為0，說明輸入數組不符合題目if lost==0:raise ValueError# 確定兩個整數的不同位，以此來做分組sep=1while lost & sep==0:sep<<=1# 第二次分組異或for i in range(len(ll)):if ll[i] & sep==0:result[0]^=ll[i]else:result[1]^=ll[i]return resultif __name__ == '__main__':ll=[3,1,3,2,2,8,1,4]print(find3(ll))

?

如果數組長度是n，該解法的時間復雜度是O(n)。把數組分成兩部分，并不需要借助額外的存儲空間，完全可以在按二進制位分組的同時來做異或運算，所以空間復雜度仍然是O(1) 。