給定一個非空整數陣列
nums，其中每個元素都出現兩次，只有一個元素只出現一次。找出那個只出現一次的元素。要求線性時間複雜度且不使用額外空間。
Example:
Input: nums = [4,1,2,1,2] Output: 4
Intuition
TIP
核心思路：XOR 的特性 a ^ a = 0，將所有數字 XOR 起來，成對的會抵消，剩下唯一的那個。
- 如果用 Hash Map 記錄出現次數，可以 O(n) 時間、O(n) 空間解決
- XOR 有三個關鍵性質：a ^ 0 = a、a ^ a = 0、XOR 滿足交換律和結合律
- 因此將所有數字依序 XOR，成對出現的數字會互相抵消為 0，最後剩下唯一的數字
Approaches
1. Hash Map Counting — O(n) / O(n)
- Idea: 用 Hash Map 記錄每個數字的出現次數，再找出只出現一次的數字
- Time:
O(n)- 遍歷陣列兩次 - Space:
O(n)- Hash Map 儲存最多 n/2 + 1 個鍵
class Solution {
fun singleNumber(nums: IntArray): Int {
val count = HashMap<Int, Int>()
for (num in nums) {
count[num] = count.getOrDefault(num, 0) + 1
}
for ((key, value) in count) {
if (value == 1) return key
}
throw IllegalArgumentException("No single number found")
}
}⭐ 2. XOR — O(n) / O(1)
- Idea: 利用 XOR 的性質，將所有數字 XOR 起來，成對的會抵消為 0，最後結果就是唯一的數字
- Time:
O(n)- 遍歷陣列一次 - Space:
O(1)- 只用一個變數
class Solution {
fun singleNumber(nums: IntArray): Int {
var result = 0
for (num in nums) {
result = result xor num
}
return result
}
}Note: Kotlin reduce
利用 Kotlin 的 reduce 函數可以更簡潔地表達：
class Solution {
fun singleNumber(nums: IntArray): Int {
return nums.reduce { acc, num -> acc xor num }
}
}🔑 Takeaways
- Pattern: XOR 消除配對是位元操作的經典技巧
- Key trick: a ^ a = 0 和 a ^ 0 = a 這兩個性質可以推廣到許多「找唯一 / 找差異」的問題