0137. Single Number II¶
题目信息¶
- 题号:
只出现一次的数字 II
- 难度:
Medium
- 主题:
数组、位运算、模计数、有限状态机
- 原题:
- 重点:
把每一位的出现次数压缩为模三状态,再用两个位掩码并行维护全部 32 位的状态转移
题目重述¶
给定非空整数数组 nums,恰有一个元素只出现一次,其余每个元素都恰好出现三次。返回这个单次元素。
进阶目标是在 O(n) 时间内只使用常量额外空间。输入与答案都按 32 位有符号整数解释。
自建示例¶
nums = [6, -9, 6, 12, 12, 6, 12]:6、12各出现三次,返回-9;nums = [-2147483648, 7, 7, 7]:答案只有最高位为一,返回 32 位最小整数;nums = [0, 4, 4, 4]:单次元素可以为零,返回0。
C++ 实现¶
#include <cstdint>
#include <unordered_map>
#include <vector>
class Solution {
private:
int countCompleteValues(const std::vector<int>& nums) {
std::unordered_map<int, int> frequency;
for (int value : nums) {
++frequency[value];
}
for (const auto& [value, count] : frequency) {
if (count == 1) {
return value;
}
}
return 0;
}
int countEveryBitModuloThree(const std::vector<int>& nums) {
long long signedResult = 0;
for (int bit = 0; bit < 32; ++bit) {
int oneCount = 0;
for (int value : nums) {
const std::uint32_t bits =
static_cast<std::uint32_t>(value);
oneCount += static_cast<int>((bits >> bit) & 1U);
}
if (oneCount % 3 == 0) {
continue;
}
if (bit == 31) {
signedResult -= 1LL << 31;
} else {
signedResult += 1LL << bit;
}
}
return static_cast<int>(signedResult);
}
int runBitwiseStateMachines(const std::vector<int>& nums) {
int seenOnce = 0;
int seenTwice = 0;
for (int value : nums) {
seenOnce = (seenOnce ^ value) & ~seenTwice;
seenTwice = (seenTwice ^ value) & ~seenOnce;
}
return seenOnce;
}
public:
int singleNumber(std::vector<int>& nums) {
return runBitwiseStateMachines(nums);
}
};
题解¶
为什么上一题的整体异或不再成立¶
相同值出现两次时 x ^ x = 0,但出现三次时 x ^ x ^ x = x。若把本题全部元素直接异或,每个三次
值反而会残留一次,与真正答案混在一起。哈希计数当然仍然正确:countCompleteValues 为每个完整整数保存
频次,再找频次一;它的 O(n) 键值状态却没有利用重复次数固定为三这一信息。
三次重复提供的新结构不再是奇偶性,而是“每一位上 1 的个数对三取模”。
方案一:独立统计每个二进制位¶
考虑固定的第 bit 位。任意三次出现的整数在此位要么贡献零个一,要么贡献三个一,模三后都为零;单次
元素若该位为一,只额外贡献一个。因此把该位在全数组中的一数量对三取模,结果恰好是答案的这一位。
countEveryBitModuloThree 对 32 位各扫描一次,使用 uint32_t 查看原值的完整比特模式。最低 31 位
按正权 2^bit 加入;最高位若为一,则按二进制补码的权值 -2^31 加入。这样
0x80000000 会重建为 -2147483648,没有对有符号负数右移,也没有把无符号最高位结果强制转换为
超出范围的正数。
该方案已经是 O(32n) = O(n) 时间和 O(1) 空间,但对数组做了 32 遍。还可以把 32 个模三计数器
的同类状态合并到位掩码中,一次输入同时推进全部位。
单个位只需要三个状态¶
对某一位,只关心目前读到的一数量模三的余数:
读到 1:0 -> 1 -> 2 -> 0
读到 0:状态保持不变
用 seenOnce 的该位为一表示余数一,用 seenTwice 的该位为一表示余数二;余数零时两者都为零。二者
不能在同一位同时为一。由于 C++ 的按位运算对整数的所有位并行执行,一对 32 位整数就能同时表示 32 个
独立状态机。
两条更新语句怎样实现状态转移¶
seenOnce = (seenOnce ^ value) & ~seenTwice
seenTwice = (seenTwice ^ value) & ~seenOnce
针对 value 中当前为一的一位:第一次出现时,第一行把 seenOnce 从零翻为一;第二次出现时,第一行
先把它清零,第二行再把 seenTwice 置一;第三次出现时,已有 seenTwice 使第一行不能置一,第二行
则通过异或清零。若输入位为零,两次异或都不改变状态。第二行必须读取更新后的 seenOnce,才能区分
“刚进入余数一”和“刚离开余数一”。
同一位累计读到一的次数 |
|
|
|---|---|---|
|
|
|
|
|
|
|
|
|
再读一次,回到 |
|
|
交错顺序为何不影响结论¶
不同整数的相同位只是在同一个模三计数器上依次加零或加一,加法模三与输入排列无关。完整 32 位又由互不
干扰的位状态机构成,所以三份相同值不必相邻。数组扫描结束后,所有三次元素在每一位的贡献都回到余数零;
单次元素的每个一位停在 seenOnce,每个零位保持零,因此 seenOnce 的完整比特模式就是答案。
负数也无需为状态机特判。最高位与其他 31 位经过完全相同的三态循环;返回 int 时它仍是原答案的
32 位有符号表示。
主解选择与复杂度¶
公开入口采用位状态机:只扫描数组一次,时间 O(n),维护两个整数,空间 O(1)。逐位计数同为常量
空间和线性渐进时间,状态更直观但需要 32 遍扫描,保留它作为从数学条件到并行状态机的中间方案。完整值
哈希计数最通用,却需 O(n) 空间,因此不满足进阶目标。