136. Single Number

Easy

Description

給定一個非空整數陣列 nums，其中每個元素都出現兩次，只有一個元素只出現一次。找出那個只出現一次的元素。要求線性時間複雜度且不使用額外空間。

Example:

Input: nums = [4,1,2,1,2] Output: 4

Intuition#

核心思路：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 計數#

概念: 用 Hash Map 記錄每個數字的出現次數，再找出只出現一次的數字
時間複雜度: O(n) - 遍歷陣列兩次
空間複雜度: 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#

概念: 利用 XOR 的性質，將所有數字 XOR 起來，成對的會抵消為 0，最後結果就是唯一的數字
時間複雜度: O(n) - 遍歷陣列一次
空間複雜度: O(1) - 只用一個變數

class Solution {
    fun singleNumber(nums: IntArray): Int {
        var result = 0
        for (num in nums) {
            result = result xor num
        }
        return result
    }
}

補充：Kotlin reduce 寫法

利用 Kotlin 的 reduce 函數可以更簡潔地表達：

class Solution {
    fun singleNumber(nums: IntArray): Int {
        return nums.reduce { acc, num -> acc xor num }
    }
}

🔑 Takeaways#

Pattern: XOR 消除配對是位元操作的經典技巧
關鍵技巧: a ^ a = 0 和 a ^ 0 = a 這兩個性質可以推廣到許多「找唯一 / 找差異」的問題