题目0260:只出现一次的数字III

题目描述

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

示例:

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

注意:

结果输出的顺序并不重要,对于上面的例子,[5, 3]也是正确答案。

你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现?

解答技巧

概述:

使用哈希表可以在$\mathcal{O}(N)$的时间复杂度和$\mathcal{O}(N)$的空间复杂度中解决该问题。

这个问题在常数的空间复杂度中解决有点困难,但可以借助两个位掩码来实现。

• 方法一:哈希表

建立一个值到频率的映射关系的哈希表,返回频率为1的数字。

算法:

from collections import Counter
class Solution:
    def singleNumber(self, nums: int) -> List[int]:
        hashmap = Counter(nums)
        return [x for x in hashmap if hashmap[x] == 1]

复杂度分析:

时间复杂度:$\mathcal{O}(N)$。

空间复杂度:$\mathcal{O}(N)$,哈希表所使用的空间。

• 方法二:两个掩码

本文将使用两个按位技巧：

• 使用异或运算可以帮助我们消除出现两次的数字;我们计算bitmask ^= x,则bitmask留下的就是出现奇数次的位。

• x & (-x)是保留位中最右边1,且将其余的1设位0的方法。

算法:

首先计算bitmask ^= x,则bitmask不会保留出现两次数字的值,因为相同数字的异或值为0。但是bitmask会保留只出现一次的两个数字(x和y)之间的差异。

我们可以直接从bitmask中提取x和y吗?不能,但是我们可以用bitmask作为标记来分离x和y。

我们通过bitmask & (-bitmask)保留bitmask最右边的1,这个1要么来自x,要么来自y。

当我们找到了x,那么y = bitmask^x。

class Solution:
    def singleNumber(self, nums: int) -> List[int]:
        # difference between two numbers (x and y) which were seen only once
        bitmask = 0
        for num in nums:
            bitmask ^= num

        # rightmost 1-bit diff between x and y
        diff = bitmask & (-bitmask)

        x = 0
        for num in nums:
            # bitmask which will contain only x
            if num & diff:
                x ^= num

        return [x, bitmask^x]

复杂度分析:

时间复杂度:$\mathcal{O}(N)$的时间遍历输入数组。

空间复杂度:$\mathcal{O}(1)$。