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

中等通过率 52.12%python3核心代码模式样例通过牛客 AC哈希位运算

牛客原题　源码

讲解章节：位运算

一句话

全体异或得到 a 异或 b，用它的最低位 1 把数组分成两组。

解题思路¶

这题考什么¶

异或的两条性质：x 异或 x = 0，0 异或 y = y。若只有一个数落单，全体异或就是答案；现在落单的有两个，全体异或得到的是 xor_all = a 异或 b，还差一步把它们分开。

分组依据：a 与 b 不相等，所以 xor_all 不为 0，它至少有一个二进制位是 1，而某一位为 1 恰恰说明 a 与 b 在这一位上不同（一个 0 一个 1）。取最低位的 1 最省事：

diff = xor_all & (-xor_all)

补码下 -x 等于 x 按位取反再加一，与原数相与只剩最低位的那个 1。按「这一位是不是 1」把数组切成两组：

a 与 b 必然落进不同组（它们在这一位上不同）
成对出现的数字必然落进同一组（值相同则每一位都相同），组内自行抵消

于是每组都变成「一个落单 + 若干成对」，各自全体异或就得到 a 与 b。位运算的基本技巧见位运算。

数据规模与复杂度¶

2 <= n <= 1000，元素取值 0 到 1e6，时限其他语言 2 秒。扫两遍数组，时间 O(n)；只用几个整数变量，空间 O(1)。两项都是题面的要求。哈希计数同样是 O(n) 时间，但要开一张 O(n) 的表，不满足空间要求。

坑在哪¶

输出必须非降序（题面提示原文「输出时按非降序排列」）。两个落单的数分别落在哪一组完全由数据决定，直接返回分组顺序有一半的概率是逆序，判题严格比对，顺序错就是错。返回前比一次大小即可。
取的必须是 xor_all 里某个为 1 的位。写成 xor_all & (xor_all - 1) 是「清掉最低位的 1」，含义正相反，用它分组会把 a 与 b 分到同一组，两组的异或结果一个是 a 异或 b、一个是 0。
分组的正确性依赖「其余数字恰好各出现两次」这个前提。若某个数出现三次，它在组内抵消不掉，结果直接失效。
判断分组时写 x & diff 是「该位为 1」，取值是 diff 而不是 1，所以不能拿它和 1 比较，只能当布尔值用。

样例复核¶

[1, 4, 1, 6]。

xor_all = 1 异或 4 异或 1 异或 6 = 4 异或 6 = 2，二进制 010
diff = 2，即第 1 位（从 0 数起）
6 的二进制 110，与 diff 相与得 2，进 a 组
4 的二进制 100，与 diff 相与得 0，进 b 组
两个 1 的二进制 001，都进 b 组并互相抵消
a = 6，b = 1 异或 4 异或 1 = 4

非降序输出 [4, 6]，与样例一致——不排序就会输出 [6, 4]。

参考实现¶

solutions/nowcoder/BM52/sol.py
from typing import List, Optional


class Solution:
    def FindNumsAppearOnce(self, nums: List[int]) -> List[int]:
        # 第一遍：成对的数字互相抵消，剩下的就是 a 异或 b
        xor_all = 0
        for x in nums:
            xor_all ^= x

        diff = xor_all & (-xor_all)     # 取最低位的 1：a 与 b 在这一位上必然不同

        # 第二遍：按 diff 这一位分成两组，a 与 b 各自落单，成对的仍在组内抵消
        a = b = 0
        for x in nums:
            if x & diff:
                a ^= x                  # 该位为 1 的一组
            else:
                b ^= x                  # 该位为 0 的一组
        return [a, b] if a < b else [b, a]      # 题面要求非降序，顺序错即判错

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