题目简述数组中除一个数只出现 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次见到某位: one1, two0第2次见到某位: one0, two1第3次见到某位: one0, two0 ← 归零完成模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]); // 3Solution::single_number(vec![0,1,0,1,0,1,99]); // 99Solution::single_number(vec![-2,-2,-2,5]); // 5 负数补码也正确要不要我把 “出现 k 次只留 1 次”的通解用 k 位状态机 / 数字逻辑 也整理一下或者顺手把 260 两个单数 Rust 版补上做成 Single Number 套题速查表
