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

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

在LeetCode上，查找只出現一次的數字是一個常見的算法問題。這類問題通常要求我們在一個數組中找出唯一一個只出現一次的數字，而其他數字都出現了兩次或多次。本文將詳細介紹如何解決這類問題，并提供多種解決方案。

問題描述

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

示例 1:

輸入: [2,2,1]
輸出: 1

示例 2:

輸入: [4,1,2,1,2]
輸出: 4

解決方案

方法一：使用哈希表

哈希表是一種常用的數據結構，可以用來存儲元素及其出現的次數。我們可以遍歷數組，將每個元素作為鍵，出現的次數作為值存儲在哈希表中。最后，我們遍歷哈希表，找出值為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)，其中n是數組的長度。我們需要遍歷數組兩次，第一次遍歷用于構建哈希表，第二次遍歷用于查找只出現一次的數字。

空間復雜度： O(n)，哈希表需要存儲數組中的每個元素及其出現的次數。

方法二：使用集合

我們可以利用集合的特性來解決問題。集合中的元素是唯一的，因此我們可以將數組中的元素添加到集合中，如果元素已經存在于集合中，則將其從集合中移除。最后，集合中剩下的元素就是只出現一次的數字。

代碼實現：

def singleNumber(nums):
    unique = set()
    for num in nums:
        if num in unique:
            unique.remove(num)
        else:
            unique.add(num)
    return unique.pop()

時間復雜度： O(n)，我們需要遍歷數組一次，每次操作的時間復雜度為O(1)。

空間復雜度： O(n)，集合需要存儲數組中的每個元素。

方法三：使用位運算

位運算是一種高效的解決方案，特別是對于這種只出現一次的數字問題。我們可以利用異或運算（XOR）的特性來解決這個問題。異或運算有以下特性：

• 任何數和0做異或運算，結果仍然是原來的數，即 a ^ 0 = a。
• 任何數和其自身做異或運算，結果是0，即 a ^ a = 0。
• 異或運算滿足交換律和結合律，即 a ^ b ^ a = b ^ a ^ a = b ^ 0 = b。

基于這些特性，我們可以將數組中的所有元素進行異或運算，最終的結果就是只出現一次的數字。

代碼實現：

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

時間復雜度： O(n)，我們只需要遍歷數組一次。

空間復雜度： O(1)，我們只使用了常數級別的額外空間。

方法四：使用數學公式

我們可以利用數學公式來解決這個問題。假設數組中有n個元素，其中n-1個元素出現了兩次，1個元素出現了一次。我們可以計算數組中所有元素的和，然后減去兩倍的所有唯一元素的和，最終的結果就是只出現一次的數字。

代碼實現：

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

時間復雜度： O(n)，我們需要遍歷數組兩次，第一次用于計算所有元素的和，第二次用于計算所有唯一元素的和。

空間復雜度： O(n)，集合需要存儲數組中的每個元素。

總結

在LeetCode上查找只出現一次的數字是一個經典的算法問題。本文介紹了四種解決方案，包括使用哈希表、集合、位運算和數學公式。每種方法都有其優缺點，具體選擇哪種方法取決于問題的約束條件和實際需求。

• 哈希表：適用于需要統計元素出現次數的場景，但空間復雜度較高。
• 集合：適用于需要快速查找和刪除元素的場景，空間復雜度較高。
• 位運算：適用于空間復雜度要求較高的場景，時間復雜度較低。
• 數學公式：適用于需要簡潔代碼的場景，但空間復雜度較高。

在實際應用中，位運算通常是最優的解決方案，因為它既高效又節省空間。然而，理解其他方法也有助于我們更好地掌握不同的算法技巧和數據結構。

參考代碼

以下是使用位運算的完整代碼示例：

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

# 測試用例
print(singleNumber([2, 2, 1]))  # 輸出: 1
print(singleNumber([4, 1, 2, 1, 2]))  # 輸出: 4

通過以上方法，我們可以輕松解決LeetCode上查找只出現一次的數字問題。希望本文對你有所幫助！