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上查找只出现一次的数字问题。希望本文对你有所帮助！