Vue.js

Appearance

On this page

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

数组中其他元素都出现三次，只有一个出现一次，找出它。

问题描述 ​

LeetCode 137. Single Number II

给你一个整数数组 nums，除某个元素仅出现一次外，其余每个元素都恰出现三次。找出那个只出现一次的元素。

要求：线性时间复杂度，常数空间。

示例：

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

思路 ​

统计每一位上 1 出现的次数，如果是 3 的倍数，说明只出现一次的数在这一位是 0，否则是 1。

解法一：按位统计 ​

javascript
function singleNumber(nums) {
  let result = 0;
  
  for (let i = 0; i < 32; i++) {
    let count = 0;
    const mask = 1 << i;
    
    for (const num of nums) {
      if (num & mask) count++;
    }
    
    if (count % 3 !== 0) {
      result |= mask;
    }
  }
  
  return result;
}

执行过程 ​

nums = [2, 2, 3, 2]
二进制：10, 10, 11, 10

位0：0+0+1+0 = 1，不是3的倍数，结果位0=1
位1：1+1+1+1 = 4，不是3的倍数，结果位1=1

结果：11 = 3

解法二：状态机 ​

用两个变量模拟"模 3 计数器"：

javascript
function singleNumber(nums) {
  let ones = 0, twos = 0;
  
  for (const num of nums) {
    ones = (ones ^ num) & ~twos;
    twos = (twos ^ num) & ~ones;
  }
  
  return ones;
}

这个方法更高效但较难理解。

状态机解释 ​

  • ones：出现 1 次的位
  • twos：出现 2 次的位
  • 出现 3 次时清零

状态转移：00 → 01 → 10 → 00

详细执行过程 ​

以 nums = [2, 2, 3, 2] 为例，用按位统计法：

二进制表示：
2 = 10
2 = 10
3 = 11
2 = 10

位 0 的统计：0 + 0 + 1 + 0 = 1，1 % 3 = 1 ≠ 0，结果位 0 = 1
位 1 的统计：1 + 1 + 1 + 1 = 4，4 % 3 = 1 ≠ 0，结果位 1 = 1

结果：11 = 3

状态机方法详解 ​

用 (twos, ones) 表示每一位出现次数对 3 取模的状态：

状态转移（当前位为 1 时）：
00 → 01（出现 1 次）
01 → 10（出现 2 次）
10 → 00（出现 3 次，清零）

状态转移（当前位为 0 时）：
保持不变

推导公式：

设输入位为 x，状态为 (twos, ones)

新 ones = (ones ^ x) & ~twos
新 twos = (twos ^ x) & ~ones

边界情况 ​

javascript
// 单个元素
singleNumber([5]);  // 5

// 负数
singleNumber([-2, -2, -2, 3]);  // 3
singleNumber([2, 2, 2, -3]);  // -3

// 0 的情况
singleNumber([0, 0, 0, 5]);  // 5

常见错误 ​

错误一：位数不够 ​

javascript
// 错误：只统计了部分位
for (let i = 0; i < 16; i++) { ... }

// 正确：统计所有 32 位
for (let i = 0; i < 32; i++) { ... }

错误二：处理负数时符号位问题 ​

JavaScript 中位运算结果是 32 位有符号整数，需要注意：

javascript
// 如果最高位为 1，结果会是负数（这是正确的）
// 不需要特殊处理，按位统计自然支持负数

通用化：其他元素出现 k 次 ​

javascript
function singleNumber(nums, k) {
  let result = 0;
  
  for (let i = 0; i < 32; i++) {
    let count = 0;
    const mask = 1 << i;
    
    for (const num of nums) {
      if (num & mask) count++;
    }
    
    if (count % k !== 0) {
      result |= mask;
    }
  }
  
  return result;
}

相关题目 ​

题目难度关键点
137. 只出现一次的数字 II中等本题
136. 只出现一次的数字简单其他出现 2 次
260. 只出现一次的数字 III中等两个只出现 1 次
面试题 17.19. 消失的两个数字困难组合应用

总结 ​

  1. 按位统计法：统计每位 1 的个数，模 3 判断
  2. 状态机法：用两个变量模拟模 3 计数器
  3. 通用思路：其他出现 k 次时，模 k 统计
  4. 时间空间：O(n) 时间，O(1) 空间

复杂度 ​

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

在 GitHub 上编辑此页