leetcode_solutions/
n2122_recover_the_original_array.rs

1/*
2 * No: 2122
3 * Title: Recover the Original Array
4 */
5
6use crate::Solution;
7
8impl Solution {
9    fn check_valid(nums: &Vec<i32>, k: i32) -> (bool, Vec<i32>) {
10        use std::collections::HashMap;
11
12        let mut counts: HashMap<i32, i32> = HashMap::new();
13        nums.clone()
14            .into_iter()
15            .for_each(|item| *counts.entry(item).or_default() += 1);
16
17        let mut ans = vec![];
18        for num in nums.iter() {
19            if counts.get_mut(&num).cloned().unwrap_or(0) == 0 {
20                continue;
21            } else if counts.get_mut(&(num + k)).cloned().unwrap_or(0) == 0 {
22                return (false, vec![]);
23            } else {
24                *counts.get_mut(&num).unwrap() -= 1;
25                *counts.get_mut(&(num + k)).unwrap() -= 1;
26                ans.push(num + k / 2);
27            }
28        }
29
30        (true, ans)
31    }
32
33    pub fn recover_array(mut nums: Vec<i32>) -> Vec<i32> {
34        nums.sort();
35
36        let len = nums.len();
37
38        for i in 1..len {
39            let k = nums[i] - nums[0];
40            if k != 0 && k % 2 == 0 {
41                let (valid, res) = Solution::check_valid(&nums, k);
42                if valid {
43                    return res;
44                }
45            }
46        }
47
48        nums
49    }
50}