LeetCode 260. 只出现一次的数字 III

约 4 分钟
文章信息 13 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 20-50 腾讯 字节 华为 美团 百度 快手 滴滴 虾皮
标签
数组 位运算

题目描述

✅ 260. 只出现一次的数字 III

image-20260928203636283

题意分析

数组中恰好有两个不同的整数各出现一次，其余每个整数都出现两次。返回这两个只出现一次的数，顺序不限。

需要在线性时间、常数额外空间内完成。整数可能为零或负数，判断依据是它们完整的二进制位模式，不能假设两个目标都为正数。

解法：异或分组

核心思路

[!blue]

异或满足 x ^ x = 0、x ^ 0 = x，且交换运算顺序不影响结果。把所有元素异或后，成对数字全部抵消，只剩两个目标数的异或 xor = a ^ b。但它还不是某个目标，需要把 a、b 分开。

因为 a != b，xor 至少有一位为 1，表示两个目标在该位上不同。选取其中任意一位作为分组依据，两个目标必然进入不同组；相同数字的位模式完全一致，它们的两份又必然进入同一组。因此每组内部再做异或，重复数字都会抵消，只留下该组唯一的目标。

lowbit = xor & -xor 可以只保留 xor 最低的一个 1。补码取负会将这一位右侧的零仍保留为零、这一位保留为一，而更高位与原数相反，所以按位与后只有这一位留下。

代码只累积选定位为零的那一组，得到 first；再利用 xor ^ first 求出另一个目标。不需要真的创建两个数组，分组仅体现在条件判断中。

解题步骤

  1. 遍历数组，将所有元素异或到 xor，得到两个目标的异或值。
  2. 计算 lowbit = xor & -xor，确定一位能区分两个目标的掩码。
  3. 再次遍历，把满足 (num & lowbit) == 0 的数字异或到 first。
  4. 返回 first 和 xor ^ first，无需对结果排序。

代码实现

class Solution {
    public int[] singleNumber(int[] nums) {
        int xor = 0;

        for (int num : nums) {
            xor ^= num;
        }

        // 两个单次数在这一位不同，用它分组后重复数仍会组内抵消。
        int lowbit = xor & -xor;
        int first = 0;

        for (int num : nums) {
            if ((num & lowbit) == 0) {
                first ^= num;
            }
        }

        return new int[] {
            first,
            xor ^ first
        };
    }
}

func singleNumber(nums []int) []int {
    xor := 0
    for _, num := range nums {
        xor ^= num
    }

    // 两个单次数在这一位不同，用它分组后重复数仍会组内抵消。
    lowbit := xor & -xor
    first := 0
    for _, num := range nums {
        if num&lowbit == 0 {
            first ^= num
        }
    }
    return []int{
        first,
        xor ^ first,
    }
}

复杂度分析

  • 时间复杂度：$O(n)$。两次遍历数组，每个元素只执行常数次位运算。
  • 空间复杂度：$O(1)$。只保存总异或值、分组掩码和一个组的异或结果，不建立分组容器。

关键点总结

[!green]

  • 总异或先消除重复项，再用两个目标的差异位把它们分开。
  • 正确分组必须同时满足：两个目标进不同组，同一重复数字的两份进同一组。
  • 选中任意一个差异位都可以，最低位只是最方便提取的一位。
  • 已知 a ^ b 和其中一个目标，再异或一次就能恢复另一个。

易错点总结

[!yellow]

  • 不能直接判断 num & xor 是否为零来分组：xor 可能包含多个差异位，两个目标都可能与它按位与得到非零值。
  • xor & (xor - 1) 是清除最低位的 1，并不是提取它；取单个位掩码应使用 xor & -xor。
  • 掩码可能位于任意位置，num & lowbit 应与零比较，不能与数值 1 比较。
  • 掩码依赖最终总异或，必须先完成第一次遍历，不能一边计算总异或一边按临时掩码分组。
  • 有符号整数按补码做位运算，即使选中符号位也能分组；掩码为负数不代表算法失效。

相似题目

题目 难度 关联与区别
136. 只出现一次的数字 简单 本题先根据两个单次值的异或差异位分组，再在每组复用原题的异或抵消。
137. 只出现一次的数字 II 中等 同样处理少量例外值，原题其他值出现三次，本题其他值出现两次但例外有两个。
补充题 192. 数组中两个只出现一次的数 中等 都用异或结果找区分两组唯一值的位；补充题还要求升序输出。
268. 丢失的数字 简单 维护异或抵消关系定位少数异常值；本题用非零位分成两组分别抵消，该题将下标与数值异或以找缺失值。
389. 找不同 简单 维护异或抵消关系定位少数异常值；本题用非零位分成两组分别抵消，该题异或两个字符串以找新增字符。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/16345207
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！