LeetCode 136: Single Number

問題描述

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

限制條件

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Each element in the array appears twice except for one element which appears only once.

範例

• Example 1:
  Input: nums = [2, 2, 1]
  Output: 1
• Example 2:
  Input: nums = [4, 1, 2, 1, 2]
  Output: 4
• Example 3:
  Input: nums = [1]
  Output: 1

解法一：暴力解

解題思路

這題最直覺的作法就是使用一個 hash table (set) 來紀錄出現過的元素，藉此找出在 nums 中只出現一次的元素。

步驟詳解

1. 初始化一個 set nums_set 用來記錄出現過的元素。
2. 從頭開始依序迭代 nums：
   1. 若當前元素 num 已經在 nums_set 中，將其從 nums_set 中移除。
   2. 若否，將其加入 nums_set 中。
3. 迭代結束後，回傳 nums_set 中剩下的唯一元素。

程式碼

def single_number(self, nums: List[int]) -> int:
	nums_set = set()

    for num in nums:
        if num in nums_set:
            nums_set.remove(num)
        else:
            nums_set.add(num)

    return nums_set.pop()

複雜度分析

• 時間複雜度：O(N)，其中 N 為 nums 的長度。
• 空間複雜度：O(N)，其中 N 為 nums 的長度。

解法二：位元運算

解題思路

根據題目，在 nums 的內的所有元素都出現兩次，只有唯一個元素只出現過一次。我們可以利用位元運算中 XOR 的特性：任何數與自身進行 XOR 運算都會等於 0（歸零律），且任何數與 0 進行 XOR 運算都會等於自身（恆等率），來找到答案。

舉例來說，若 nums 為 [3, 3, 2, 2, 1]，若我們將每個數字依序進行 XOR 運算，我們會得到 (3 ^ 3) ^ (2 ^ 2) ^ 1 = 0 ^ 0 ^ 1 = 1 的結果。 由這個例子可知，只要是出現兩次（偶數次）的數字都會因為歸零律的關係最終等於 0，最後只有那個只出現一次的元素會被保留。

步驟詳解

1. 初始化 xor 為 0 來儲存每次進行 XOR 運算的結果。
2. 從頭依序迭代 nums，並將每次迭代中的當前元素 num 對 xor 進行 XOR 運算。
3. 最後回傳 xor。

程式碼

def single_number(self, nums: List[int]) -> int:
    xor = 0
    for num in nums:
        xor ^= num
    return xor

複雜度分析

• 時間複雜度：O(N)，其中 N 為 nums 的長度。
• 空間複雜度：O(1)。

參考資料

• LeetCode 原題出處：Single Number – LeetCode