题目描述

[EN | CN]

给定一个整数数组 nums,其中恰好有 两个 元素只出现 一次,其余所有元素均出现 两次。 找出只出现一次的那两个元素。

示例:

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

注意:

  • 结果输出的顺序并不重要,对于上面的例子,[5, 3] 也是正确答案。
  • 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现?

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

与《LeetCode 136. 只出现一次的数字 ⌨️》的解法 1 类似,用集合保存出现奇数次的元素,返回遍历结束之后剩下的 2 个元素。

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

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(n)$,额外空间存储。

实现与结果如下:

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

解法 2:位运算

精彩!该做法要对位运算比较熟才行。

与《LeetCode 136. 只出现一次的数字 ⌨️》的解法 4 有些类似,如果只有一个元素只出现了一次,那么全部异或一下就可以得到它。但是本题中有两个元素出现了一次(假设为 ab),那么我们全部异或只能得到 ab 异或的结果(假设为 c)。

我们仔细思考 c 是什么?如果 c 上的某一位为 1,说明 ab 的该位相同;如果某一位为 1,那么 ab 的该位不同。根据这一点,其实我们就可以将原数组分成分别带有 ab 的两组。假设 c 的第 k 位为 1,那么按照「第 k 位是否为 1」可以将原数组分成两个子数组,ab 必定被分开,而数组中的其他元素出现的次数也一定是偶数次,此时我们再应用同样的思路对子数组进行全部异或,就可以得到 ab 的值。

有几点要注意:

  • 为了避免额外的空间消耗,我们不需要真正地给子数组分配空间,只需要在遍历的时候将其中的一个子数组与初始值为 0 的一个数(假设为 d)异或即可,最终得到的 d 是其中一个结果,另一个结果是 dc 的异或结果。
  • 怎么取 c 中的一个 1?我们知道在计算机中数字的二进制是以 补码 形式保存的,而补码就是 反码 加一,因此 c & -c与操作)就可以得到「除了 c 的最后一位保留为 1 以外其他位全部为 0」的 mask。例如:
  • 68 的原码、反码、补码都为 0100 0100
    • -68 的原码为 1100 0100,反码为 1011 1011,补码为 1 1011 1100
    • 68-68 进行与操作的结果为 0000 0100
  • 得到只有第 k 位为 1、其他位都为 0 的 mask 之后,怎么判断一个数的第 k 位为 10?只需要进行 与操作 即可,若这个数的第 k 位为 1,那么得到的结果等于 mask;若第 k 位为 0,则得到的结果等于 0

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

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

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
from functools import reduce
class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        a_xor_b = reduce(lambda a, b: a ^ b, nums)
        rightest_diff_mask = a_xor_b & -a_xor_b

        x = 0
        for num in nums:
            if num & rightest_diff_mask:
                x ^= num

        return [x, x ^ a_xor_b]
  • 执行用时:44 ms,在所有 Python3 提交中击败了 83.69% 的用户。
  • 内存消耗:15 MB,在所有 Python3 提交中击败了 6.25% 的用户。