1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| struct Solution;
// @lc code=start
impl Solution {
/// ## 解题思路
/// - 位运算
/// 1. 设nums的唯一一次元素为ans;
/// 2. 各数第i位二进制位均为0,1, 如果先将其他数第i位相加,
/// 由于这些数都出现了3次, 所以相加后结果必定为3的倍数;
/// 3. 最后加上ans的第i位, 则结果 %3 的余数和ans的第i位一样;
/// 4. 因此分别计算各位的和后%3, 如果不为0, 则置1;
pub fn single_number0(nums: Vec<i32>) -> i32 {
let mut res = 0;
for i in 0..32 {
// 计算第i位的bit和
if nums.iter().map(|&n| (n >> i) & 1_i32).sum::<i32>() % 3 != 0 {
// 如果第i位的bit和不为3的倍数, 则该位为1
res |= (1 << i);
}
}
res
}
/// - 位运算2
/// 1. 在上面基础上优化, 同时计算所有位数;
/// 2. 用(ai,bi)表示第i位累加和 mod 3 后的结果;
/// 3. (ai,bi) 总共有3总情况:(00), (01), (10)
/// 4. (ai,bi) ^ ni
/// (ai, bi) ^ ni (ai', bi')
/// (0, 0) 0 -> (0, 0)
/// (0, 0) 1 -> (0, 1)
/// (0, 1) 0 -> (0, 1)
/// (0, 1) 1 -> (1, 0)
/// (1, 0) 0 -> (1, 0)
/// (1, 0) 1 -> (0, 0)
/// 5. ai' = (!ai & bi & ni) | ( ai & !bi & !ni)
/// bi' = (!ai & !bi & ni) | (!ai & bi & !ni) = !ai & (bi ^ ni)
/// 6. 最后结果取b
pub fn single_number(nums: Vec<i32>) -> i32 {
nums.iter()
.fold((0, 0), |(a, b), &n| (a ^ n & !b, a & n | b & !n))
.0
}
/// 计算a, b, 改为交替计算
pub fn single_number3(nums: Vec<i32>) -> i32 {
let (mut a, mut b) = (0, 0);
for n in nums {
a = !b & (a ^ n);
b = !a & (b ^ n);
}
a
}
}
// @lc code=end
|