java 異或_異或運算的妙用

LeetCode No.136 隻出現一次的數字

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

說明：

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

示例 1:

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

示例 2:

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

解法：時間複雜度為O(N)，不開辟新的記憶體空間。根據題眼，“其餘每個元素均出現兩次”，可以聯想到位運算中的「異或」，它的Java表示為^，規則是：「相異置1，相同置0，0與任何數異或結果為任何數」。這樣，我們就可以用0與數組中的每個元素異或，與第一個元素異或的結果一定為第一個元素，如果後續有和第一個元素相同的元素，那麼結果重新置為0。那麼，最終循環結束得到的結果就是題目所求。

代碼如下：

class Solution { public int singleNumber(int[] nums) { int res = 0; for(int num : nums){ res ^= num; } return res; }}
           

運作結果：

成功​執行用時: 1 ms, 在Single Number的Java送出中擊敗了99.44% 的使用者​記憶體消耗: 28.6 MB, 在Single Number的Java送出中擊敗了33.50% 的使用者