题目描述

[EN | CN]

给定一个非空整数数组,除了某个元素只出现 一次 以外,其余每个元素均出现 两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

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

示例 2:

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

解法 1:集合保存出现奇数次的元素

遍历数组,用一个集合(set)来保存已经遍历过 奇数次 的元素,也就是说对于每一个新来的元素,判断是否在集合中,是的话则在集合中删除该元素,否则将元素加入集合中。

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(n)$,需要遍历一遍;
  • 空间复杂度为 $O(n)$,需要集合保存出现了奇数次的数组。

实现与结果如下:

1
2
3
4
5
6
7
8
9
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        odd_set = set()
        for n in nums:
            if n in odd_set:
                odd_set.remove(n)
            else:
                odd_set.add(n)
        return odd_set.pop()
  • 执行用时:52 ms,在所有 Python3 提交中击败了 69.54% 的用户。
  • 内存消耗:15.7 MB,在所有 Python3 提交中击败了 5.61% 的用户。

解法 2:与集合求和的倍数做差

因为数组中只有一个元素只出现了一遍,其他元素都出现了两边,那么我们可以将该数组转为集合,然后计算集合的和,乘以 2 再减去数组的和,就得到了那个只出现了一遍的元素。

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(n)$,需要遍历;
  • 空间复杂度为 $O(n)$,需要保存集合。

实现与结果如下:

1
2
3
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return sum(set(nums)) * 2 - sum(nums)
  • 执行用时:36 ms, 在所有 Python3 提交中击败了 97.14% 的用户。
  • 内存消耗:15.6 MB, 在所有 Python3 提交中击败了 5.61% 的用户。

解法 3:位运算

位运算中的 异或XOR)有很好的性质来处理这种问题:

  • 一个数 $a$ 与自身异或等于 $0$,即 $a \otimes a = 0$。
  • 一个数 $a$ 与 $0$ 异或等于 $a$ 自身,即 $a \otimes 0 = a$。
  • 异或操作满足交换律和结合律,即 $a \otimes b \otimes a = a \otimes a \otimes b = 0 \otimes b = b$。

因此我们只需要对所有的数过一遍异或操作,就可以得到那个唯一的数字。

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(n)$,需要遍历;
  • 空间复杂度为 $O(1)$,只需要保存一个数。

实现与结果如下:

1
2
3
4
from functools import reduce
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda a, b: a ^ b, nums)
  • 执行用时:40 ms,在所有 Python3 提交中击败了 92.52% 的用户。
  • 内存消耗:15.3 MB,在所有 Python3 提交中击败了 14.02% 的用户。

解法 4:按位统计

统计每一位(个位、十位等等)出现的数字的个数,出现的次数是奇数的数字就是该位的结果。

假设数组长度为 $n$,最长的数字的长度是 $m$,那么

  • 时间复杂度为 $O(mn)$,需要遍历一遍;
  • 空间复杂度为 $O(1)$,只需要保存一个数。

实现与结果略。