LeetCode 137. 只出现一次的数字 II —— 位运算解法

题目描述

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

你必须设计并实现 线性时间复杂度 且使用 常数级空间 的算法。

示例 1：

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

示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99

提示：

• 1 <= nums.length <= 3 * 10^4

• -2^31 <= nums[i] <= 2^31 – 1

• 除某个元素仅出现一次外，其余每个元素都恰出现三次

解题思路

这道题是 位运算经典题，可以用 按位统计 的方法解决。

方法 1：按位统计（简单易理解）

C 语言实现

int singleNumber(int* nums, int numsSize) {
int bit[32] = {0};

// 统计每一位1的个数
for (int i = 0; i < numsSize; i++) {
for (int j = 0; j < 32; j++) {
bit[j] += (nums[i] >> j) & 1;
}
}

int result = 0;

// 取模3并还原结果
for (int j = 0; j < 32; j++) {
if (bit[j] % 3) {
result |= (1u << j); // 注意用 unsigned 避免符号位报错
}
}

return result;
}

⚠️ 注意：

• 1 << 31 可能会出现 未定义行为，因为 1 是 signed int

• 用 1u << j 可以安全操作符号位

方法 2：状态机位运算（更优雅）

这个方法用 两个变量 ones 和 twos 表示每一位出现次数的状态：

• ones：该位出现过 1 次

• twos：该位出现过 2 次

• 当某位出现 3 次时，自动归零

核心公式：

ones = (ones ^ num) & ~twos;
twos = (twos ^ num) & ~ones;

最终 ones 就是只出现一次的数字。

代码示例：

int singleNumber(int* nums, int numsSize) {
int ones = 0, twos = 0;
for (int i = 0; i < numsSize; i++) {
ones = (ones ^ nums[i]) & ~twos;
twos = (twos ^ nums[i]) & ~ones;
}
return ones;
}

• 时间复杂度：O(n)

• 空间复杂度：O(1)

总结

• 本题核心是 位运算 + 计数取模

• 方法 1 用 32 位数组，易理解，但空间稍大

• 方法 2 用 状态机位运算，常数空间，面试更加加分

• 注意 符号位左移 的写法，要用 unsigned int 避免运行错误

💡 拓展思路：

• 如果数字出现次数不是 3，而是其他 k，按位统计仍然适用

• 方法 2 的状态机也可以扩展到 k 次出现的情况