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

/*
 * No: 2122
 * Title: Recover the Original Array
 */

use crate::Solution;

impl Solution {
    fn check_valid(nums: &Vec<i32>, k: i32) -> (bool, Vec<i32>) {
        use std::collections::HashMap;

        let mut counts: HashMap<i32, i32> = HashMap::new();
        nums.clone()
            .into_iter()
            .for_each(|item| *counts.entry(item).or_default() += 1);

        let mut ans = vec![];
        for num in nums.iter() {
            if counts.get_mut(&num).cloned().unwrap_or(0) == 0 {
                continue;
            } else if counts.get_mut(&(num + k)).cloned().unwrap_or(0) == 0 {
                return (false, vec![]);
            } else {
                *counts.get_mut(&num).unwrap() -= 1;
                *counts.get_mut(&(num + k)).unwrap() -= 1;
                ans.push(num + k / 2);
            }
        }

        (true, ans)
    }

    pub fn recover_array(mut nums: Vec<i32>) -> Vec<i32> {
        nums.sort();

        let len = nums.len();

        for i in 1..len {
            let k = nums[i] - nums[0];
            if k != 0 && k % 2 == 0 {
                let (valid, res) = Solution::check_valid(&nums, k);
                if valid {
                    return res;
                }
            }
        }

        nums
    }
}