leetcode_solutions/
n2007_find_original_array_from_doubled_array.rs

1/*
2 * No: 2007
3 * Title: Find Original Array From Doubled Array
4 */
5
6use crate::Solution;
7
8impl Solution {
9    pub fn find_original_array(changed: Vec<i32>) -> Vec<i32> {
10        use std::collections::HashMap;
11
12        if changed.len() % 2 != 0 {
13            return vec![];
14        }
15
16        let mut changed = changed.clone();
17        changed.sort();
18
19        let mut original: Vec<i32> = vec![];
20
21        let mut element_indexes: HashMap<i32, usize> = HashMap::new();
22        changed.iter().enumerate().for_each(|(_, val)| {
23            *element_indexes.entry(*val).or_insert(0) += 1;
24        });
25
26        print!("{:?}", element_indexes);
27
28        for value in changed.into_iter() {
29            let count = *element_indexes.get(&value).unwrap();
30            if count != 0 {
31                original.push(value);
32                let double = value * 2;
33                if element_indexes.contains_key(&double) && element_indexes[&double] > 0 {
34                    element_indexes.insert(double, element_indexes[&double] - 1);
35                } else {
36                    return vec![];
37                }
38
39                let count = *element_indexes.get(&value).unwrap();
40                element_indexes.insert(value, count - 1);
41            }
42        }
43
44        print!("{:?}", element_indexes);
45
46        original
47    }
48}