Vue.js

Appearance

On this page

实战：只出现一次的数字 III ​

数组中有两个数只出现一次，其他都出现两次，找出这两个数。

问题描述 ​

LeetCode 260. Single Number III

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

示例：

输入：nums = [1,2,1,3,2,5]
输出：[3,5]

思路 ​

  1. 所有数异或得到 a ^ b
  2. 找到 a ^ b 中任意一个为 1 的位
  3. 按这一位把数组分成两组，a 和 b 分别在两组中
  4. 两组分别异或得到 a 和 b

解法 ​

javascript
function singleNumber(nums) {
  // 1. 得到 a ^ b
  let xor = 0;
  for (const num of nums) {
    xor ^= num;
  }
  
  // 2. 找到最右边的 1
  const rightmostBit = xor & (-xor);
  
  // 3. 分组异或
  let a = 0, b = 0;
  for (const num of nums) {
    if (num & rightmostBit) {
      a ^= num;
    } else {
      b ^= num;
    }
  }
  
  return [a, b];
}

执行过程 ​

nums = [1, 2, 1, 3, 2, 5]

1. xor = 1^2^1^3^2^5 = 3^5 = 6 = 110

2. rightmostBit = 6 & -6 = 010 = 2

3. 按第2位分组：
   第2位为1：[2, 2, 3] → 异或得 3
   第2位为0：[1, 1, 5] → 异或得 5

结果：[3, 5]

为什么分组有效？ ​

a 和 b 至少有一位不同（否则相等），用这一位分组：

  • a 和 b 必定在不同组
  • 相同的数必定在同一组（会抵消）

复杂度 ​

  • 时间：O(n)
  • 空间：O(1)

详细执行过程 ​

以 nums = [1, 2, 1, 3, 2, 5] 为例：

第一步：全部异或
  1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5
= (1 ^ 1) ^ (2 ^ 2) ^ 3 ^ 5
= 0 ^ 0 ^ 3 ^ 5
= 3 ^ 5 = 6

6 的二进制：110

第二步：找最右边的 1
  6 & -6 = 110 & ...11111010 = 010 = 2

第三步：按第 2 位分组
  第 2 位为 1：2, 2, 3 → 2 ^ 2 ^ 3 = 3
  第 2 位为 0：1, 1, 5 → 1 ^ 1 ^ 5 = 5

结果：[3, 5]

n & (-n) 的原理 ​

n & (-n) 提取 n 的最低位 1：

n  = 01100 (12)
-n = 10100 (-12 的补码)
n & (-n) = 00100 (4)

原理：-n = ~n + 1，取反加 1 后，最低位 1 右边全变 0，左边全取反

边界情况 ​

javascript
// 两个数相邻
singleNumber([1, 2, 2, 3]);  // [1, 3]

// 包含负数
singleNumber([-1, 0, -1, 2]);  // [0, 2]

// 两个数差很大
singleNumber([1, 1, 2147483647, -2147483648]);  // [2147483647, -2147483648]

常见错误 ​

错误一：分组位选择错误 ​

javascript
// 错误：随意选一个不同位
const diff = xor & 1;  // 可能是 0

// 正确：找最低位 1（保证不为 0）
const rightmostBit = xor & (-xor);

错误二：分组条件写错 ​

javascript
// 错误：用等于 rightmostBit
if ((num & rightmostBit) === rightmostBit) { ... }

// 正确：用不等于 0
if (num & rightmostBit) { ... }

两种写法等价，但第二种更简洁。

错误三：忘记一个数 ​

javascript
// 错误：只分了一组
let a = 0;
for (const num of nums) {
  if (num & rightmostBit) a ^= num;
}
// 漏了 b

// 正确：两组都要处理
let a = 0, b = 0;
for (const num of nums) {
  if (num & rightmostBit) a ^= num;
  else b ^= num;
}

与 Single Number I/II 对比 ​

题目条件解法
136 (I)其他 2 次，1 个 1 次全部异或
137 (II)其他 3 次，1 个 1 次按位统计模 3
260 (III)其他 2 次，2 个 1 次分组异或

相关题目 ​

题目难度关键点
260. 只出现一次的数字 III中等本题
136. 只出现一次的数字简单基础异或
137. 只出现一次的数字 II中等按位统计
面试题 17.19. 消失的两个数字困难类似思路

总结 ​

  1. 核心思路：先异或得 a^b，再分组各自异或
  2. 分组依据：a^b 中任意一个为 1 的位
  3. 技巧：n & (-n) 提取最低位 1
  4. 时间空间：O(n) 时间，O(1) 空间

在 GitHub 上编辑此页