LeetCode 136: Single Number

Description

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.

Constraints

• 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.

Examples

• 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

Solution 1: Brute-Force

Thought

The most intuitive approach for this problem is to use a hash table (set) to record the elements that have appeared. This allows us to identify the elements that appear only once in nums.

Steps

1. Initialize a set nums_set to record the elements that have appeared.
2. Iterate through nums sequentially from the beginning:
   1. If the current element num is already in nums_set, remove it from nums_set.
   2. If not, add it to nums_set.
3. After the iteration, return the unique element remaining in nums_set.

Codes

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()

Complexities

• Time Complexity: O(N),  where N represents the length of nums.
• Space Complexity: O(N),  where N represents the length of nums.

Solution 2: Bit-Manipulation

Thought

According to the problem, all elements in nums appear twice, except for one element that appears only once. We can leverage the XOR operation’s properties in bitwise manipulation: XORing any number with itself results in 0, and XORing any number with 0 results in the number itself. This allows us to find the answer efficiently.

For example, if nums is [3, 3, 2, 2, 1], by performing XOR operation on each number sequentially, we get (3 ^ 3) ^ (2 ^ 2) ^ 1 = 0 ^ 0 ^ 1 = 1. From this example, we can see that any number appearing twice (even number of times) will eventually become 0 due to the zero property, and only the element that appears once will be retained.

Steps

1. Initialize xor as 0 to store the result of each XOR operation.
2. Iterate through nums sequentially from the beginning, and perform XOR operation on the current element num with xor in each iteration.
3. Finally, return xor.

Codes

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

Complexities

• Time Complexity: O(N),  where N represents the length of nums.
• Space Complexity: O(1).

References

• LeetCode link: Single Number – LeetCode