LeetCode: 136 Single Number

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

Example:

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

Example:

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

Example:

Input: nums = [1]
Output: 1

问题

给定一个非空整数数组 nums，其中每个元素都出现两次，只有一个元素出现一次。找出那个只出现一次的元素。

解决方案 1

使用异或操作

Approach 1 / 方法 1

This solution uses the XOR bitwise operation. The idea is that XOR-ing two identical numbers results in 0, and XOR-ing any number with 0 results in the number itself. Thus, XOR-ing all the numbers in the array will leave us with the single number that appears only once.

该解决方案使用异或位操作。其思想是异或两个相同的数字结果为0，任何数字与0异或的结果是数字本身。因此，异或数组中的所有数字将留下只出现一次的单个数字。

Implementation / 实现

python

# Solution 1 implementation in Python
def singleNumber(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

Explanation / 解释

1. Step 1 / 第一步:

• Initialize result to 0.
  初始化 result 为 0。

2. Step 2 / 第二步:

• Iterate through each number in nums.
  遍历 nums 中的每个数字。

3. Step 3 / 第三步:

• XOR the current number with result.
  当前数字与 result 进行异或运算。

4. Step 4 / 第四步:

• Return the final value of result, which is the single number.
  返回 result 的最终值，即单个数字。

Complexity Analysis / 复杂度分析

• Time Complexity: O(n), where n is the number of elements in the array.
  时间复杂度: O(n)，其中n是数组中的元素数量。

• Space Complexity: O(1), since we are using a constant amount of additional space.
  空间复杂度: O(1)，因为我们使用了固定数量的额外空间。

Key Concept / 关键概念

• XOR bitwise operation to efficiently find the single number in a list where every other number appears twice.
  使用异或位操作高效地在每个数字都出现两次的列表中找到单个数字。

解决方案 2

使用哈希表

Approach 2 / 方法 2

This solution uses a hash table to keep track of the count of each number. The idea is to iterate through the array and update the count of each number in the hash table. Then, iterate through the hash table to find the number with a count of 1.

该解决方案使用哈希表来跟踪每个数字的计数。其思想是遍历数组并更新哈希表中每个数字的计数。然后遍历哈希表找到计数为1的数字。

Implementation / 实现

python

# Solution 2 implementation in Python
def singleNumber(nums):
    hashmap = {}
    for num in nums:
        if num in hashmap:
            hashmap[num] += 1
        else:
            hashmap[num] = 1
    for num in hashmap:
        if hashmap[num] == 1:
            return num

Explanation / 解释

1. Step 1 / 第一步:

• Initialize an empty hash table hashmap.
  初始化一个空的哈希表 hashmap。

2. Step 2 / 第二步:

• Iterate through each number in nums.
  遍历 nums 中的每个数字。

3. Step 3 / 第三步:

• Update the count of the current number in the hash table.
  更新哈希表中当前数字的计数。

4. Step 4 / 第四步:

• Iterate through the hash table and return the number with a count of 1.
  遍历哈希表并返回计数为1的数字。

Complexity Analysis / 复杂度分析

• Time Complexity: O(n), where n is the number of elements in the array.
  时间复杂度: O(n)，其中n是数组中的元素数量。

• Space Complexity: O(n), for storing the counts in the hash table.
  空间复杂度: O(n)，用于在哈希表中存储计数。

Key Concept / 关键概念

• Using a hash table to count occurrences of each number and identify the single one.
  使用哈希表计数每个数字的出现次数并识别单个数字。

Comparison / 比较

Comparison Between All Approaches

1. Algorithm:

   • Approach 1 (XOR Operation):

     • Uses the XOR bitwise operation to find the single number.

   • Approach 2 (Hash Table):

     • Uses a hash table to count occurrences of each number.

2. Efficiency:

   • Time Complexity:

     • Both approaches have a time complexity of O(n), where n is the number of elements in the array.

   • Space Complexity:

     • The XOR method has a space complexity of O(1).
     • The hash table method has a space complexity of O(n).

3. Readability and Maintainability:

   • Approach 1 (XOR Operation):

     • Simple, efficient, and uses minimal space.

   • Approach 2 (Hash Table):

     • More intuitive for those unfamiliar with bitwise operations but uses more space.

4. Best Practice:

   • Recommended Solution: Approach 1 (XOR Operation):
     • Reason: Approach 1 is preferred due to its simplicity, efficiency, and minimal space usage.

Summary / 总结

• Use Approach 1 for a simple, efficient, and space-saving solution.
• Approach 1’s XOR bitwise operation is straightforward and effective.

Tips / 提示

• Familiarize yourself with bitwise operations to leverage efficient solutions.
• Ensure to handle edge cases such as arrays with only one element.

Solution Template for similar questions / 提示

• Use bitwise operations for problems involving pairs and unique elements.
• Implement hash table methods for counting occurrences when needed.

What does the main algorithm of this question aim to test? / 这个问题的主要算法旨在测试什么？

Understanding of bitwise operations and their application in finding unique elements in arrays.

5 more similar questions / 推荐5问题

1. LeetCode 137. Single Number II
2. LeetCode 260. Single Number III
3. LeetCode 268. Missing Number
4. LeetCode 389. Find the Difference
5. LeetCode 645. Set Mismatch

Recommended Resources:

Single Number – Leetcode 136 – Python by NeetCode