題目
難度：★☆☆☆☆
類型：數(shù)組
給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次。找出那個只出現(xiàn)了一次的元素。
說明：
你的算法應(yīng)該具有線性時間復(fù)雜度售担。 你可以不使用額外空間來實現(xiàn)嗎？
示例
示例 1:
輸入: [2,2,1]
輸出: 1
示例 2:
輸入: [4,1,2,1,2]
輸出: 4
解答
方案1：統(tǒng)計次數(shù)
我們準備一個字典署辉，字典的鍵是列表中出現(xiàn)過的數(shù)字族铆，值是該數(shù)字出現(xiàn)的次數(shù)，遍歷數(shù)組統(tǒng)計每個數(shù)字出現(xiàn)的次數(shù)哭尝，最后返回出現(xiàn)過一次的數(shù)字即可哥攘。
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
count = {} # 定義字典
for num in nums: # 遍歷數(shù)組
if num in count: # 如果字典中存在當前記錄
count[num] += 1 # 次數(shù) + 1
else: # 否則
count[num] = 1 # 當前數(shù)加入到字典中，且出現(xiàn)次數(shù)為1
count = {v: k for k, v in count.items()} # 字典鍵值交換
return count[1] # 返回出現(xiàn)一次的數(shù)字
方案2：列表
準備一個列表材鹦，遍歷數(shù)組逝淹，當前數(shù)字不在列表中時，加入列表桶唐，如果在列表中栅葡，則彈出列表中的該數(shù)，則最后只有出現(xiàn)過奇數(shù)次的數(shù)字留在列表中尤泽，返回該數(shù)即可欣簇。
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
temp = [] # 定義空列表
for num in nums: # 遍歷數(shù)組
if num in temp: # 如果列表中存在當前數(shù)
temp.remove(num) # 移除
else: # 否則
temp.append(num) # 當前數(shù)加入到列表
return temp[0] # 返回列表中剩下的數(shù)字
方案3：巧用異或
異或運算有這樣的特性：
交換律：a ^ b == b ^ a
相同數(shù)字異或為零：a ^ a == 0
數(shù)字異或零為該數(shù)字：a ^ 0 == a
根據(jù)以上的三條特性，我們可以得到坯约，如果將數(shù)組中所有數(shù)字用異或符號連接起來熊咽，則出現(xiàn)偶數(shù)次的數(shù)字失效，最終結(jié)果為出現(xiàn)奇數(shù)次的數(shù)字的異或闹丐。
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = 0
for num in nums:
res ^= num
return res
或者直接用字符串网棍，內(nèi)存占用多些。
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return eval('^'.join(map(str, nums)))
如有疑問或建議妇智，歡迎評論區(qū)留言~
