LeetCode如何找出只出現一次的數字

# LeetCode如何找出只出現一次的數字

## 問題描述

在LeetCode題庫中，"只出現一次的數字"（Single Number）是一個經典的算法問題。題目描述如下：

> 給定一個非空整數數組，其中某個元素只出現一次，其余每個元素均出現兩次。找出那個只出現了一次的元素。

示例：
- 輸入: [2,2,1]
- 輸出: 1
- 輸入: [4,1,2,1,2]
- 輸出: 4

## 解決方案

### 方法一：暴力解法（雙重循環）

最直觀的解決方法是使用雙重循環遍歷數組，統計每個數字出現的次數：

```python
def singleNumber(nums):
    for i in range(len(nums)):
        found = False
        for j in range(len(nums)):
            if i != j and nums[i] == nums[j]:
                found = True
                break
        if not found:
            return nums[i]

時間復雜度：O(n2)
空間復雜度：O(1)

方法二：哈希表法

利用哈希表（字典）存儲數字出現次數：

def singleNumber(nums):
    count = {}
    for num in nums:
        if num in count:
            count[num] += 1
        else:
            count[num] = 1
    for num in count:
        if count[num] == 1:
            return num

時間復雜度：O(n)
空間復雜度：O(n)

方法三：數學運算

利用集合和數學公式 2*(a+b+c) - (a+a+b+b+c) = c：

def singleNumber(nums):
    return 2 * sum(set(nums)) - sum(nums)

時間復雜度：O(n)
空間復雜度：O(n)

方法四：位運算（最優解）

利用異或（XOR）運算的特性： - 任何數和0異或都是它本身：a ^ 0 = a - 任何數和自身異或都是0：a ^ a = 0 - 異或滿足交換律和結合律

def singleNumber(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

時間復雜度：O(n)
空間復雜度：O(1)

算法分析

異或運算的深入理解

異或運算的二進制表現：

5 ^ 3 = 6
  101 (5)
^ 011 (3)
= 110 (6)

在本題中的應用：

[4,1,2,1,2]
4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1^1) ^ (2^2) = 4 ^ 0 ^ 0 = 4

復雜度對比

變種問題

變種1：數字出現兩次，只有一個出現一次

這是標準問題，直接用異或解法即可。

變種2：數字出現三次，只有一個出現一次

此時異或不再適用，需要改用其他方法：

def singleNumber(nums):
    ones = twos = 0
    for num in nums:
        ones = (ones ^ num) & ~twos
        twos = (twos ^ num) & ~ones
    return ones

變種3：所有數字出現兩次，有兩個不同的數字各出現一次

需要分組異或：

def singleNumber(nums):
    xor = 0
    for num in nums:
        xor ^= num
    
    mask = 1
    while (xor & mask) == 0:
        mask <<= 1
    
    a, b = 0, 0
    for num in nums:
        if num & mask:
            a ^= num
        else:
            b ^= num
    return [a, b]

實際應用

這類算法在以下場景中有實際應用： 1. 數據校驗：檢測數據傳輸中的異常值 2. 加密算法：某些加密技術利用異或特性 3. 硬件設計：數字電路中的奇偶校驗

總結

通過這個問題，我們學習了： 1. 暴力解法雖然直觀但效率低下 2. 哈希表法是通用解法 3. 數學方法展示了巧妙的思路 4. 位運算解法是最優方案

關鍵點：理解異或運算的特性是解決此類問題的核心。對于面試和算法競賽，位運算解法通常是考察重點。

擴展練習

建議嘗試以下LeetCode類似題目： - 137. Single Number II - 260. Single Number III - 268. Missing Number

掌握這些問題的解法，可以深入理解位運算在算法中的應用。

參考代碼

完整測試用例：

if __name__ == "__main__":
    test_cases = [
        ([2,2,1], 1),
        ([4,1,2,1,2], 4),
        ([1], 1)
    ]
    
    for nums, expected in test_cases:
        assert singleNumber(nums) == expected
    print("All test cases passed!")

通過系統化的學習和練習，這類問題將不再困難。記?。豪斫鈫栴}本質比死記硬背解法更重要。 “`