[260][中等] 只出现一次的数字 III

题目描述

260. 只出现一次的数字 III

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

示例 :

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

注意：

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

解题思路

此题与[136][简单] 只出现一次的数字有类似之处. 然而数组中会有两个只出现一次的数字(当然这两个数字不相等). 直接使用136中的解法得到是数字a和b的异或结果, 无法进一步将这两个数字从它们的异或结果中分离.

一个思路就是能不能把原始的一个数组, 分成两个数组, 而且两个单独出现的数字被分到不同的数组中, 而且同一个数字在存在在一个数组中. 这样分别对两个数组使用136中的方法, 就能分开找到这两个数字了.

分组的依据很直观地可以想到依据a和b异或的结果进行分类. 重新审视两数异或的结果, 结果中值为1的位, 说明两个数在此位置上的值不同, 从而找到了分组的依据. 整体步骤如下:

• 对数组中所有数字进行累计异或计算, 得到两个单独出现数a和b的异或值

• 选取异或中任意一位值为1的位置(例如最左侧的值为1的位置), 再次对数组进行循环, 计算每个数与上一步结果即a^b的异或, 根据选取位的结果, 将结果为0的分为1组, 结果为1的分为一组

• 再对每组分别进行累计异或, 找到这两个单独出现的数字

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        res1 = 0
        for num in nums:
            res1 ^= num

        loc = 1
        for i in range(32):
            if (res1 >> i) & 1 == 1:
                break
            loc <<= 1

        res_0, res_1 = 0, 0
        for num in nums:
            if num & loc == 0:
                res_0 ^= num
            else:
                res_1 ^= num

        return [res_0, res_1]