0137. Single Number II
======================
题目信息
--------
:题号: 0137. 只出现一次的数字 II
:难度: Medium
:主题: 数组、位运算、模计数、有限状态机
:原题: `LeetCode 0137 `_
:重点: 把每一位的出现次数压缩为模三状态,再用两个位掩码并行维护全部 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++ 实现
--------
.. code-block:: cpp
#include
#include
#include
class Solution {
private:
int countCompleteValues(const std::vector& nums) {
std::unordered_map 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& 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(value);
oneCount += static_cast((bits >> bit) & 1U);
}
if (oneCount % 3 == 0) {
continue;
}
if (bit == 31) {
signedResult -= 1LL << 31;
} else {
signedResult += 1LL << bit;
}
}
return static_cast(signedResult);
}
int runBitwiseStateMachines(const std::vector& 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& 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 个模三计数器
的同类状态合并到位掩码中,一次输入同时推进全部位。
单个位只需要三个状态
~~~~~~~~~~~~~~~~~~~~~~
对某一位,只关心目前读到的一数量模三的余数:
.. code-block:: text
读到 1:0 -> 1 -> 2 -> 0
读到 0:状态保持不变
用 ``seenOnce`` 的该位为一表示余数一,用 ``seenTwice`` 的该位为一表示余数二;余数零时两者都为零。二者
不能在同一位同时为一。由于 C++ 的按位运算对整数的所有位并行执行,一对 32 位整数就能同时表示 32 个
独立状态机。
两条更新语句怎样实现状态转移
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
.. code-block:: text
seenOnce = (seenOnce ^ value) & ~seenTwice
seenTwice = (seenTwice ^ value) & ~seenOnce
针对 ``value`` 中当前为一的一位:第一次出现时,第一行把 ``seenOnce`` 从零翻为一;第二次出现时,第一行
先把它清零,第二行再把 ``seenTwice`` 置一;第三次出现时,已有 ``seenTwice`` 使第一行不能置一,第二行
则通过异或清零。若输入位为零,两次异或都不改变状态。第二行必须读取更新后的 ``seenOnce``,才能区分
“刚进入余数一”和“刚离开余数一”。
.. list-table::
:header-rows: 1
* - 同一位累计读到一的次数
- ``seenOnce`` 位
- ``seenTwice`` 位
* - ``0 mod 3``
- ``0``
- ``0``
* - ``1 mod 3``
- ``1``
- ``0``
* - ``2 mod 3``
- ``0``
- ``1``
* - 再读一次,回到 ``0 mod 3``
- ``0``
- ``0``
交错顺序为何不影响结论
~~~~~~~~~~~~~~~~~~~~~~
不同整数的相同位只是在同一个模三计数器上依次加零或加一,加法模三与输入排列无关。完整 32 位又由互不
干扰的位状态机构成,所以三份相同值不必相邻。数组扫描结束后,所有三次元素在每一位的贡献都回到余数零;
单次元素的每个一位停在 ``seenOnce``,每个零位保持零,因此 ``seenOnce`` 的完整比特模式就是答案。
负数也无需为状态机特判。最高位与其他 31 位经过完全相同的三态循环;返回 ``int`` 时它仍是原答案的
32 位有符号表示。
主解选择与复杂度
~~~~~~~~~~~~~~~~
公开入口采用位状态机:只扫描数组一次,时间 ``O(n)``,维护两个整数,空间 ``O(1)``。逐位计数同为常量
空间和线性渐进时间,状态更直观但需要 32 遍扫描,保留它作为从数学条件到并行状态机的中间方案。完整值
哈希计数最通用,却需 ``O(n)`` 空间,因此不满足进阶目标。