260. Single Number III
1.題目說明:給定一個整數陣列 nums,其中正好有兩個元素只出現一次,其餘的元素都出現了兩次。請找出這兩個只出現一次的元素。
要求:
- 時間複雜度為 O(n)(線性)
- 空間複雜度為 O(1)(常數)
2.解法思路(使用位運算)
這題的巧妙解法是利用 位元 XOR(^) 的特性來完成:
3.XOR 性質:
- a ^ a = 0
- a ^ 0 = a
- XOR 運算具有交換律與結合律
4.步驟如下:
1.先把所有數字 XOR 起來,最後會得到 a ^ b(因為其他成對的數字都會變成 0 被抵消)。
2.a ^ b 的結果不為 0,表示 a 和 b 至少有一個位元不同(也就是 1)。
3.找到這個 XOR 結果中 任意一個為 1 的位元位置(我們通常找最右邊的 1)。
4.用這個位元來將原陣列的數字分成兩組:
- 一組這個位元是 0
- 一組這個位元是 1
5.在這兩組中,各自再做一次 XOR,就能分別得到 a 和 b。
5.範例輸入輸出
輸入:nums = [1,2,1,3,2,5]
執行流程:
- XOR 所有數字得:3 ^ 5 = 6
- 找出 6 最右邊的 1 → diff = 2
- 分組後 XOR:
- 組一:1, 1, 2, 2 → XOR = 0
- 組二:3, 5 → XOR = 3 和 5
輸出:[3, 5]
6.程式碼截圖:
7.學習心得:此次題目我自認為比較難,但這也是給我一個學習的機會,從AI問答中學習到這題的學習重點,之後還是會找類似的題目去做練習。