数组中只出现一次的两个数字

数组中只出现一次的两个数字_牛客题霸_牛客网

问题简述

一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

思路：位运算

• 异或运算的性质：

  性质1：0^a = a
  性质2：a^a = 0
  性质3（交换律）：a^b = b^a
  性质4（结合律）：(a^b)^c = a^(b^c)

• 根据性质1 和性质2，可以构造如下算法：

  定义 all_xor(arr) := arr[0] ^ arr[1] ^ .. ^ arr[-1]
  记这两个不同的数分别为 a 和 b
  则 ab = a ^ b = all_xor(arr)  # 存在两个相同数字的都被消去
  因为 a != b，则 ab 的二进制表示中必然有一个为 1（因为 0^1=1）
  根据这个位置的 1 将 nums 分为两组，则 a 和 b 分别在这两组数字中，分别求一次 all_xor 即可；

Python

class Solution:
    def FindNumsAppearOnce(self , arr: List[int]) -> List[int]:
        
        ab = 0  # 计算 a ^ b
        for x in arr:
            ab ^= x
            
        r = ab & (~ab + 1)  # 计算 ab 最右侧的 1
        
        a = b = 0
        for x in arr:  # 根据 r 位置是否为 1 将 arr 分为两组
            if r & x:
                a ^= x
            else:
                b ^= x
        
        return [a, b] if a < b else [b, a]