這是一道看完答案會覺得很簡單，但做之前很難想到答案的題目！！！

不信？

Let us go ！

題目描述

給定一個非空整數數組，除了某個元素只出現一次以外，其餘每個元素均出現兩次。找出那個只出現了一次的元素。

說明：

你的演算法應該具有線性時間複雜度。 你可以不使用額外空間來實現嗎？

示例 1:

輸入: [2,2,1]

輸出: 1

示例 2:

輸入: [4,1,2,1,2]

輸出: 4

題目解析

根據題目描述，由於加上了時間複雜度必須是O(n)，並且空間複雜度為O(1)的條件，因此不能用排序方法，也不能使用map數據結構。

小吳想了一下午沒想出來，答案是使用 位操作Bit Operation 來解此題。

將所有元素做異或運算，即a[1] ⊕ a[2] ⊕ a[3] ⊕ …⊕ a[n]，所得的結果就是那個只出現一次的數字，時間複雜度為O(n)。

異或

異或運算A ⊕ B的真值表如下：

AB⊕FFFFTTTFTTTF

動畫演示

進階版

有一個 n 個元素的數組，除了兩個數只出現一次外，其餘元素都出現兩次，讓你找出這兩個只出現一次的數分別是幾，要求時間複雜度為 O(n) 且再開闢的內存空間固定(與 n 無關)。

示例 :

輸入: [1,2,2,1,3,4]

輸出: [3,4]

題目再解析

根據前面找一個不同數的思路演算法，在這裡把所有元素都異或，那麼得到的結果就是那兩個只出現一次的元素異或的結果。

然後，因為這兩個只出現一次的元素一定是不相同的，所以這兩個元素的二進位形式肯定至少有某一位是不同的，即一個為 0 ，另一個為 1 ，現在需要找到這一位。

根據異或的性質 任何一個數字異或它自己都等於 0，得到這個數字二進位形式中任意一個為 1 的位都是我們要找的那一位。

再然後，以這一位是 1 還是 0 為標準，將數組的 n 個元素分成兩部分。

• 將這一位為 0 的所有元素做異或，得出的數就是只出現一次的數中的一個
• 將這一位為 1 的所有元素做異或，得出的數就是只出現一次的數中的另一個。

這樣就解出題目。忽略尋找不同位的過程，總共遍曆數組兩次，時間複雜度為O(n)。

動畫再演示

End

本題的基礎版來源於 LeetCode 第 136 號問題：只出現一次的數字。雖然題目難度是 簡單，但解法真的很巧妙。感興趣的同學可以根據思路去回答一下：https://leetcode-cn.com/problems/single-number/ 。

作者：五分鐘學演算法

原文：https://www.cnblogs.com/fivestudy/p/10275446.html

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！