企业官网建设流程全解析

题目简述

数组中除一个数只出现 1 次外，其余都出现 3 次，找出这个单数。

要求 O(n) 时间 / O(1) 空间，不能用哈希计数。

思路和 Python 版完全一致：用模 3 状态机对每一位做计数。

✅ 推荐实现：位运算状态机（O(1) 空间，最标准）

Rust 的
“i32” 是补码表示，位运算天然支持负数，直接返回
“one” 即可，不用手动处理符号位。

impl Solution {
pub fn single_number(nums: Vec) -> i32 {
let mut one = 0i32; // 该位出现次数 ≡ 1 (mod 3)
let mut two = 0i32; // 该位出现次数 ≡ 2 (mod 3)

for x in nums { one = (one ^ x) & !two; two = (two ^ x) & !one; } one }

}

状态转移含义（和 Python 同构）

第1次见到某位: one=1, two=0
第2次见到某位: one=0, two=1
第3次见到某位: one=0, two=0 ← 归零，完成模3

“!two” 是 Rust 的按位取反（对应 Python 的
“~two”）。

🔧 备选：逐位统计法（更好理解，处理符号位显式）

impl Solution {
pub fn single_number(nums: Vec) -> i32 {
let mut res = 0i32;
for bit in 0…32 {
let mask = 1u32 << bit;
let mut cnt = 0u32;
for &x in &nums {
if (x as u32) & mask != 0 {
cnt += 1;
}
}
if cnt % 3 == 1 {
res |= 1i32 << bit;
}
}
res
}
}

这里把
“i32” cast 成
“u32” 看位，最后直接当补码返回，负数也正确。

复杂度

维度 状态机版 逐位版
时间 O(n) O(32n) ≈ O(n)
空间 O(1) O(1)

三语言对照（136/137 系列）

语言 核心代码
Python
“one=(one^x)&~two; two=(two^x)&~one”
Rust
“one=(one^x)&!two; two=(two^x)&!one”
TS
“one=(one^x)&~two; two=(two^x)&~one”

Rust 用
“!” 按位取反，Python/JS 用
“~”，语义完全一样。

为什么不用 HashMap

“HashMap” 计数是 O(n) 时间但 O(n) 空间，违反题目隐藏约束（面试会被追问“能不能 O(1) 空间”）。

小验证

// LeetCode 样例
Solution::single_number(vec![2,2,3,2]); // 3
Solution::single_number(vec![0,1,0,1,0,1,99]); // 99
Solution::single_number(vec![-2,-2,-2,5]); // 5 （负数补码也正确）

要不要我把 “出现 k 次只留 1 次”的通解（用 k 位状态机 / 数字逻辑） 也整理一下，或者顺手把 260 两个单数 Rust 版补上做成 Single Number 套题速查表？