leetcode/
single_numbers.rs

1//! # 剑指 Offer 56 - I. 数组中数字出现的次数
2//!
3//! 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
4//!
5//! 难度：中等
6//!
7//! ## 示例 1：
8//!
9//! ```text
10//! 输入：nums = [4,1,4,6]
11//! 输出：[1,6] 或 [6,1]
12//! ```
13//!
14//! ## 示例 2：
15//!
16//! ```text
17//! 输入：nums = [1,2,10,4,1,4,3,3]
18//! 输出：[2,10] 或 [10,2]
19//! ```
20//!  
21//!
22//! ## 限制：
23//!
24//! `2 <= nums.length <= 10000`
25//!
26//! See [leetcode](https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/)
27
28pub struct Solution;
29
30impl Solution {
31
32    /// - 异或运算，消除出现了再次的数字，剩下就是要找的目标数字的异或结果 a ^ b
33    /// - 再通过区分最低位的 1 把数组分成两部分，即每个部分只会包含一个目标数字。每个部分异或运算，可以找出这部分里的目标数字
34    /// - 另一个目标数字可以用同样的方式找出
35    /// - 更简单的方式是直接把已经找出的一个目标数字写之前两个目标异或的结果进行异或操作 (a ^ b ^ a = b)。
36    pub fn single_numbers(nums: Vec<i32>) -> Vec<i32> {
37        assert!(nums.len() >= 2 && nums.len() <= 10000);
38
39        let xor = nums.iter().fold(0, |xor, x| xor ^ x);
40
41        let mut helper = 1;
42        while xor & helper == 0 {
43            helper <<= 1;
44        }
45        let a = nums.iter().filter(|&x| x & helper == 0).fold(0, |a, x| a ^ x);
46        vec![a, xor ^ a]
47    }
48}
49
50#[cfg(test)]
51mod tests {
52    use super::Solution;
53
54    #[test]
55    fn test() {
56        let t = |v| {
57            let mut r = Solution::single_numbers(v);
58            r.sort();
59            r
60        };
61
62        assert_eq!(vec![1,6], t(vec![4,1,4,6]));
63        assert_eq!(vec![2,10], t(vec![1,2,10,4,1,4,3,3]));
64    }
65}
leetcode/single_numbers.rs

leetcode/
single_numbers.rs
