260 只出现一次的数字 III

标签: 位运算

题目

题目链接：260 只出现一次的数字 III 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

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

示例 1：

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。

示例 2：

输入：nums = [-1,0]
输出：[-1,0]

示例 3：

输入：nums = [0,1]
输出：[1,0]

提示：

2 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
除两个只出现一次的整数外，nums 中的其他数字都出现两次

思路

1. 步骤：
   1. 全员异或：由于「两个只出现一次的整数外，nums 中的其他数字都出现两次」，并且异或的性质之一是「两个相同的数进行异或等于0」，那么可以考虑对全数组进行异或，以抵消出现了两次的数字。因此，全数组进行异或等价于这两个只出现一次的数字进行异或。
   2. 找到异或值为1的那一位：得到两个数字进行异或的结果，那么找到异或值为 1 的那一位，说明这两个数字在该位上不相同。
   3. 根据异或结果分组：然后，以这个数字为基准，再 分别 对整个数组进行异或，根据异或结果将整个数组分为 2 组，即「数组中在该位上为 1 的数字」A 组 和「数组中在该位上为 0 的数字」B 组.
   4. 组内异或：因为其他数字都出现过两次，那么这些出现的两次的相同数字要么在 A 组，要么在B 组 中。在组内进行异或，可以消除这些出现过两次的数字，分别得到只出现过一次的数字。

代码

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        # 全员异或一下
        xor = 0
        for i in nums:
            xor ^= i 

        # 找到异或值中为 1 的那一位
        anc = 0
        for i in range(32):
            if 1 << i & xor != 0:
                anc = i 
                break
        
        # 将数组分为 2 组
        # 组内进行异或，能够得到答案
        res1, res2 = 0, 0
        for i in nums:
            if 1 << anc & i != 0:
                res1 ^= i 
            else:
                res2 ^= i 
        return [res1, res2]