巧用異或
異或規律
異或有以下規律
0^N = NN^N = 0- 交換律
a ^ b = b ^ a - 結合律
a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c - 自反性
a ^ b ^ a = b
使用異或交換數據
一般的交換方式, 利用臨時變數:
a = 1
b = 2
temp = a
a = b
b = temp
但你也可以使用異或的方法交換:
a = 1
b = 2
a = a ^ b # 1 ^ 2
b = a ^ b # 1 ^ 2 ^ 2 = 1
a = a ^ b # 1 ^ 2 ^ 1 = 2
三次異或操作, 交換兩個變數的值
注意: 異或交換變數時, 不能為引用類型, 否則為被清空
解決一些演算法題
出現奇數次的1個數字
問題位置: 劍指 Offer II 070. 排序數組中只出現一次的數字
問題描述:
給定一個只包含整數的有序數組 nums ，每個元素都會出現兩次，唯有一個數只會出現一次，請找出這個唯一的數字。
示例 1:
輸入: nums = [1,1,2,3,3,4,4,8,8]
輸出: 2
示例 2:
輸入: nums = [3,3,7,7,10,11,11]
輸出: 10
題解:
非常簡單, 由於異或的自反性(a ^ b ^ a = b), 所以只要將全部數異或, 那麼得到的肯定是只出現一次的那個數
程式碼
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
eor = 0
for i in nums:
eor = eor ^ i
return eor
出現奇數次的2個數字
題目位置: 劍指 Offer 56 – I. 數組中數字出現的次數
問題描述:
一個整型數組nums里除兩個數字之外，其他數字都出現了兩次。請寫程式找出這兩個只出現一次的數字。
要求時間複雜度是O(n)，空間複雜度是O(1)。
示例 1：
輸入：nums = [4,1,4,6]
輸出：[1,6] 或 [6,1]
示例 2：
輸入：nums = [1,2,10,4,1,4,3,3]
輸出：[2,10] 或 [10,2]
題解:
假設不同的兩個數為a和b
由於有兩個數, 我們無法通過一次異或得到, 但是我們可以通過一次異或得到a ^ b
由於a和b不可能相等, 那麼, a ^ b != 0, 即 a ^ b的二進位位一定至少會有一個 “1”
# 如
arr = [1, 1, 2, 2, 3, 4]
# 全部異或得到 3 ^ 4 != 0
# 二進位位:
011
100
-------
111
根據這一點, 我們可以把數據分為兩半: 某一位有”1″和某一位無”1″, a和b就分別在這兩半中
接下來, 只需要對這兩半數據全部異或即可得到兩個數a和b
思路已經清晰了, 現在的重點要確定 “某一位” 時第幾位, 我們需要提取出來, 不然沒將數對半分
如何做呢? 記住 一個數最後位的1 等於 一個數 與上 自己取反+1 即可, 下面是解釋:
eor = 101011100
right_one = eor & (~eor + 1)
"""
eor = 101011100
~eor = 010100011
~eor+1 = 0101000100
& 0000000100
"""
程式碼
class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
eor = 0
# 同樣先全部異或
for i in nums:
eor = eor ^ i
# 確定eor最右邊的1
right_one = eor & (~eor + 1)
eor2 = 0
for i in nums:
# 將數據分為兩半, &right_one = 0 或 != 0
if right_one & i == 0:
# 繼續異或, 得到第一個數
eor2 = eor2 ^ i
# eor ^ eor2 得到第二個數
eor = eor ^ eor2
return eor, eor2
