- 異或運(yùn)算：如果a亏吝、b兩個(gè)值不相同岭埠，則異或結(jié)果為1。如果a蔚鸥、b兩個(gè)值相同惜论，異或結(jié)果為0。
- 題目一：136. Single Number【 leetcode】
一個(gè)整型數(shù)組里除了一個(gè)數(shù)字之外止喷，其他的數(shù)字都出現(xiàn)了偶數(shù)次馆类。請(qǐng)寫(xiě)程序找出這一個(gè)只出現(xiàn)一次的數(shù)字。
思路：任何一個(gè)數(shù)字異或它自己都等于0启盛；與0異或都等于它本身
# -*- coding:utf-8 -*-
class Solution:
# 返回[a,b] 其中ab是出現(xiàn)一次的兩個(gè)數(shù)字
def FindNumsAppearOnce(self, array):
# write code here
res = 0
for i in range(len(array)):
res ^= array[i]
return res
- 題目二：
一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外蹦掐，其他的數(shù)字都出現(xiàn)了偶數(shù)次。請(qǐng)寫(xiě)程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字僵闯。
思路：
# -*- coding:utf-8 -*-
class Solution:
# 返回[a,b] 其中ab是出現(xiàn)一次的兩個(gè)數(shù)字
def FindNumsAppearOnce(self, array):
# write code here
xor = 0
for i in range(len(array)):
xor ^= array[i]
mark = 1
#找到從低位到高位訪問(wèn)XOR的第一個(gè)等于1的那一位
while xor & mark == 0:
mark <<= 1
#然后根據(jù)該位是否為1卧抗，將數(shù)組分成兩個(gè)子數(shù)組,分別取求異或
res1,res2 =0 ,0
for i in range(len(array)):
if array[i]&mark == 0:
res1 ^= array[i]
else:
res2 ^= array[i]
return [res1,res2]
題目三：
有一個(gè)數(shù)組，每個(gè)數(shù)字都出現(xiàn)了3次鳖粟，除了其中的某一個(gè)只出現(xiàn)了1次社裆。找出這個(gè)只出現(xiàn)了1次的數(shù)字。
思路：這個(gè)題的做法是把32位的二進(jìn)制數(shù)進(jìn)行遍歷向图，統(tǒng)計(jì)每個(gè)數(shù)字的每一位出現(xiàn)的和泳秀。因?yàn)槊總€(gè)數(shù)字出現(xiàn)了3次或者1次，所以如果某一位出現(xiàn)的次數(shù)不是3次榄攀，那么這個(gè)位置一定是因?yàn)槟莻€(gè)只出現(xiàn)1次的數(shù)字導(dǎo)致的嗜傅。用來(lái)保存結(jié)果的res是0，因此使用或操作檩赢，就能把這個(gè)位置的數(shù)字變成1.該問(wèn)題也可以用字典哈希來(lái)做吕嘀，但是那樣的話空間復(fù)雜度為O(n)
# -*- coding:utf-8 -*-
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = 0
for i in range(32):
cnt = 0
#統(tǒng)計(jì)32位中的每一位出現(xiàn)1的次數(shù)
mask = 1 << i
for num in nums:
if num & mask:
cnt += 1
#如果該位上出現(xiàn)1的次數(shù)不能被3整除，則一定是因?yàn)槲ㄒ坏哪莻€(gè)出現(xiàn)一次的數(shù)導(dǎo)致的
if cnt % 3 == 1:
#保留該位，與res求或運(yùn)算
res |= mask
#以后出現(xiàn)位運(yùn)算的時(shí)候偶房，需要對(duì)結(jié)果進(jìn)行判斷一下最好趁曼。
# 如果不在這個(gè)范圍內(nèi)，說(shuō)明了結(jié)果被認(rèn)為是無(wú)符號(hào)的數(shù)了棕洋，需要減去2 ^ 32
if res >= 2 ** 31:
res -= 2 ** 32
return res
