leetcode/
set_mismatch.rs

1//! # 645. 错误的集合
2//!
3//! 难度 简单
4//!
5//! 集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。
6//!
7//! 给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
8//!
9//! ## 示例 1:
10//!
11//! ```text
12//! 输入: nums = [1,2,2,4]
13//! 输出: [2,3]
14//! ```
15//!
16//! ## 注意:
17//!
18//! - 给定数组的长度范围是 `[2, 10000]`。
19//! - 给定的数组是无序的。
20//!
21//! See [leetcode](https://leetcode-cn.com/problems/set-mismatch/)
22
23/// 异或操作
24pub struct Solution;
25impl Solution {
26    pub fn find_error_nums(nums: Vec<i32>) -> Vec<i32> {
27        let len = nums.len();
28        let xor = (1..len as i32 + 1).fold(0, |xor, x| xor ^ x);
29        let xor = nums.iter().fold(xor, |xor, x| xor ^ x);
30
31        let mut helper = 1;
32        while xor & helper == 0 {
33            helper <<= 1;
34        }
35
36        let mut xor0 = 0;
37        let mut xor1 = 0;
38        (1..len as i32 + 1).chain(nums.iter().map(|&x| x)).for_each(|x| {
39            if x & helper == 0 {
40                xor0 ^= x;
41            } else {
42                xor1 ^= x;
43            }
44        });
45        match nums.iter().any(|&x| x == xor0) {
46            true => vec![xor0, xor1],
47            false => vec![xor1, xor0],
48        }
49    }
50}
51
52#[cfg(test)]
53mod tests {
54    use super::Solution;
55
56    #[test]
57    fn test() {
58        assert_eq!(&[2,3][..], Solution::find_error_nums(vec![1,2,2,4]));
59    }
60}
leetcode/set_mismatch.rs

leetcode/
set_mismatch.rs
