LeetCode136：只出現(xiàn)一次的數(shù)字
標(biāo)簽：位運(yùn)算、哈希表
給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次疯兼。找出那個(gè)只出現(xiàn)了一次的元素。
說(shuō)明：
你的算法應(yīng)該具有線(xiàn)性時(shí)間復(fù)雜度贫途。 你可以不使用額外空間來(lái)實(shí)現(xiàn)嗎吧彪？
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/single-number
解法一：暴力法
直接每個(gè)挨個(gè)找，時(shí)間復(fù)雜度
解法二：哈希表法
遍歷數(shù)組的同時(shí)丢早，將遍歷到的元素與哈希表現(xiàn)存的元素進(jìn)行比較姨裸，若已存在，存value值為2怨酝，否則存為1傀缩。最后檢索整個(gè)數(shù)組，返回值為1的元素
時(shí)間復(fù)雜度
空間復(fù)雜度
class Solution {
public int singleNumber(int[] nums) {
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
if(map.containsKey(nums[i])){
map.put(nums[i],2);
continue;
}
map.put(nums[i],1);
}
for(int i=0;i<nums.length;i++){
if(map.get(nums[i])==1)
return nums[i];
}
return -1;
}
}
解法三：異或法
如果我們對(duì) 0 和二進(jìn)制位做 XOR 運(yùn)算农猬，得到的仍然是這個(gè)二進(jìn)制位
a⊕0=a
如果我們對(duì)相同的二進(jìn)制位做 XOR 運(yùn)算赡艰，返回的結(jié)果是 0
a⊕a=0
XOR 滿(mǎn)足交換律和結(jié)合律
a⊕b⊕a=b
所以我們只需要將所有的數(shù)進(jìn)行 XOR 操作，得到那個(gè)唯一的數(shù)字
時(shí)間復(fù)雜度
空間復(fù)雜度
class Solution {
public int singleNumber(int[] nums) {
for(int i=1;i<nums.length;i++){
nums[0]=nums[0] ^ nums[i];
}
return nums[0];
}
}
