一個整型數組裡除了兩個數字之外，其他的數字都出現了兩次。
請寫程序找出這兩個只出現一次的數字。
看題目描述很簡單，那麼，如何解決呢？
思路1 — 雙重循環查找
最簡單的方案是兩層循環比較。實現非常簡單：
<code>def get_two_diff(arr): result = [] for i in range(len(arr)): for j in range(len(arr)): if arr[i] == arr[j] and i != j: break else: result.append(arr[i]) return result/<code>
這樣做的時間複雜度是 O(n^2)，空間複雜度是 O(1)
這個時間複雜度顯然太高了。
思路2 — 排序後遍歷
通過排序，我們只要找到下一個及上一個數與當前數均不同的數即是我們要找的數。這個算法的時間、空間複雜度主要取決於排序算法的時間、空間複雜度。通過快速排序，我們可以實現空間複雜度 O(1)，時間複雜度 O(nlogn) 的排序。通過基數排序，我們可以實現空間複雜度 O(n)，時間複雜度 O(n) 的排序。
下面的代碼是基於基數排序的算法：
<code>def get_two_diff(arr): for i in range(len(str(max(arr)))): bucket_list = [[] for _ in range(10)] for a in arr: bucket_list[int(a / (10 ** i)) % 10].append(a) arr = [y for x in bucket_list for y in x] return [arr[i] for i in range(len(arr)) if (0 < i < len(arr) - 1 and arr[i - 1] != arr[i] != arr[i + 1]) or (i == 0 and arr[i] != arr[i + 1] or i == len(arr) - 1 and arr[i] != arr[i - 1])]/<code>
思路3 — 空間換時間，使用 hashmap
依賴哈希表數據查找的時間複雜度為 O(1) 的特性，使用 hash 表可以讓我們通過分別遍歷一次數組和哈希表完成算法的求解，從而通過增長為 O(n) 的空間複雜度，將算法的時間複雜度降為 O(n)
<code>def get_two_diff(arr): numdict = {} for a in arr: numdict[a] = 1 if numdict.get(a) is None else 2 return [a for a in numdict if numdict[a] == 1]/<code>思路4 — 按位異或
如果題目變成一個數組裡除了一個數字之外，其他數字都出現兩次，找到這一個數字，我們很容易就可以實現了。因為兩個相同數字異或等於 0，一個數和 0 異或還是它本身，利用這一特性，將數組中所有數字異或，最終出現兩次的所有數字異或結果為 0，只有出現一次的數字與 0 異或返回了它本身，於是我們找到了這個只出現了一次的數字。但題目中出現一次的數字是兩個不相同的數，所以如果我們仍然將所有數字異或，最終將會得到這兩個不相同數字的異或結果，我們是否有辦法在異或的結果中將兩個數字還原為原來的數字或轉化為尋找數組中只出現一次的一個數字呢？辦法是有的，既然兩個數字是不同的，那麼最終的異或結果一定不為 0，而這個結果數字中，為 1 的位表示兩個出現一次的數中，這兩位不同。假設異或結果的數字中，第 n 位為 1，則說明兩個只出現一次的數字中，一個第 n 位為 1，一個第 n 位為 0，我們可以將原數組劃分為兩個數組，分別是所有第 n 位為 0 的數組成的數組和所有第 n 位為 1 的數組成的數組，這樣既可以保證所有相同的數都被放入同一個數組，也可以保證兩個只出現了一次的數分別被放入兩個不同的數組，於是，最終我們將問題轉化為找到分別在兩個數組找到每個數組中只出現一次的一個數字。
<code>def get_two_diff(arr): num = 0 for a in arr: num ^= a first_set_index = get_first_set_bit(num) base = 1 for i in range(1, first_set_index): base *= 2 num0 = num1 = 0 for a in arr: if a & base == 0: num0 ^= a else: num1 ^= a return num0, num1def get_first_set_bit(num, bit=1): if num & 1 == 1: return bit return get_first_set_bit(num / 2, bit + 1)/<code>
於是我們實現了時間複雜度 O(n)，空間複雜度 O(1) 的算法實現。
閱讀更多 湛神帶你寫代碼 的文章
