題目：
給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外几迄，其余每個元素均出現(xiàn)兩次社露。找出那個只出現(xiàn)了一次的元素。
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
說明：
你的算法應(yīng)該具有線性時間復(fù)雜度衅枫。 你可以不使用額外空間來實現(xiàn)嗎？
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
示例 1:
輸入: [2,2,1]
輸出: 1
示例 2:
輸入: [4,1,2,1,2]
輸出: 4
解題思路：
- 排序數(shù)組朗伶，如果某個數(shù)與前后兩個數(shù)均不相等則該數(shù)只出現(xiàn)一次弦撩。
- 哈希映射，key 為每個數(shù)的值论皆，value 為每個數(shù)出現(xiàn)的頻率益楼。最后找到 value = 1 的數(shù)返回。
- 異或運算点晴，直接進行異或操作求值感凤。不使用額外空間。
異或運算（XOR）解題是最優(yōu)雅的解法粒督，且不使用額外空間陪竿，其概念為：
- 如果我們對 0 和二進制位做 XOR 運算，得到的仍然是這個二進制位
- a XOR 0 = a
- 如果我們對相同的二進制位做 XOR 運算屠橄，返回的結(jié)果是 0
- a XOR a = 0
- XOR 滿足交換律和結(jié)合律
代碼：
借助哈希表：
Java:
哈希映射頻率（可用于字符串出現(xiàn)頻率的計算）
class Solution {
public int singleNumber(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
Integer count = map.get(num); //get() 方法獲取元素不存在時返回null
count = count == null ? 1 : ++count; //count為null 時證明元素不存在族跛，則頻率改為1，否則count頻率+1
map.put(num, count); //加入映射表
}
for (Integer num : map.keySet())
if (map.get(num) == 1) return num; //返回頻率為1的數(shù)
return 0;
}
}
Python：
1锐墙、借助 try...except...礁哄，只適用于該題中重復(fù)元素重復(fù)出現(xiàn)次數(shù)為偶數(shù)次。
class Solution(object):
def singleNumber(self, nums):
hash_map = {}
for i in nums:
try:
hash_map.pop(i) # 嘗試移除該數(shù)
except:
hash_map[i] = 1 # 移除失敗證明字典內(nèi)沒有該值溪北，則添加到字典
return hash_map.popitem()[0] #最后字典中只剩下一個鍵值對桐绒，返回其鍵值
2、字典映射頻率（可用于字符串出現(xiàn)頻率的計算）
class Solution:
def singleNumber(self, nums: List[int]) -> int:
hash_map = {}
for num in nums:
hash_map.setdefault(num, 0)
hash_map[num] += 1 # 每次出現(xiàn)頻率加一
for k, v in hash_map.items(): #二次遍歷返回頻率為1的數(shù)
if v == 1:
return k
return 0
亦或運算(XOR)：
其處理邏輯可以簡單理解為：
輸入: [2 , 3 , 2 , 4 , 3] , 初始化 result = 0
result = 0 XOR 2 = 2
result = 2 XOR 3 = [2 , 3]
result = [2 , 3] XOR 2 = 3
result = 3 XOR 4 = [3 , 4]
result = [3 , 4] XOR 3 = 4
返回 result = 4
異或運算是位操作中最基本運算之一刻盐，以上是為方便理解異或運算而簡化抽象的邏輯掏膏，如果想進一步了解位操作可以參考Wiki百科劳翰。
高級程序設(shè)計語言異或運算表示符號一般是 ^敦锌。
Java:
class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for (int num : nums)
result = result ^ num;
return result;
}
}
Python:
class Solution:
def singleNumber(self, nums: List[int]) -> int:
result = 0
for num in nums:
result = result ^ num
return result
歡迎關(guān)注微.信公.眾號愛寫B(tài)ug
