LeetCode每日一题(2007. Find Original Array From Doubled Array)

An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.

Example 1:

Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]

Explanation: One possible original array could be [1,3,4]:

• Twice the value of 1 is 1 * 2 = 2.
• Twice the value of 3 is 3 * 2 = 6.
• Twice the value of 4 is 4 * 2 = 8.
  Other original arrays could be [4,3,1] or [3,1,4].

Example 2:

Input: changed = [6,3,0,1]
Output: []

Explanation: changed is not a doubled array.

Example 3:

Input: changed = [1]
Output: []

Explanation: changed is not a doubled array.

Constraints:

• 1 <= changed.length <= 105
• 0 <= changed[i] <= 105

---

这题的关键是， 对 changed 进行排序， 然后按顺序找 double， 因为如果不按顺序我们检查一个数要检查2 和/2 两种情况， 但是排序之后我们只需要检查2 的值是否存在即可。 建一个 HashMap 维护当前所有剩余值的数量。最后注意 0 这个特殊情况

---

use std::collections::HashMap;

impl Solution {
    pub fn find_original_array(mut changed: Vec<i32>) -> Vec<i32> {
        if changed.len() % 2 == 1 {
            return vec![];
        }
        changed.sort();
        let mut m: HashMap<i32, i32> = changed.iter().fold(HashMap::new(), |mut m, &v| {
            *m.entry(v).or_insert(0) += 1;
            m
        });
        let mut ans = Vec::new();
        for &v in &changed {
            if let Some(c) = m.remove(&v) {
                if v == 0 {
                    if c < 2 {
                        return vec![];
                    }
                    ans.push(v);
                    if c > 2 {
                        m.insert(0, c - 2);
                    }
                    continue;
                }
                if let Some(d) = m.remove(&(v * 2)) {
                    ans.push(v);
                    if d - 1 > 0 {
                        m.insert(v * 2, d - 1);
                    }
                    if c - 1 > 0 {
                        m.insert(v, c - 1);
                    }
                    continue;
                }
                return vec![];
            }
            continue;
        }
        ans
    }
}
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