LeetCode/2007.find-original-array-from-doubled-array.cpp at master · samba9274/LeetCode · GitHub

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/*
 * @lc app=leetcode id=2007 lang=cpp
 *
 * [2007] Find Original changedrray From Doubled changedrray
 *
 * https://leetcode.com/problems/find-original-array-from-doubled-array/description/
 *
 * algorithms
 * Medium (38.40%)
 * Likes:    785
 * Dislikes: 55
 * Total changedccepted:    53.2K
 * Total Submissions: 137K
 * Testcase Example:  '[1,3,4,2,6,8]'
 *
 * changedn 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 <= 10^5
 * 0 <= changed[i] <= 10^5
 *
 *
 */

// @lc code=start
class Solution
{
public:
    vector<int> findOriginalArray(vector<int> &changed)
    {
        if (changed.size() % 2)
            return {};
        unordered_map<int, int> c;
        for (int a : changed)
            c[a]++;
        vector<int> keys;
        for (auto it : c)
            keys.push_back(it.first);
        sort(keys.begin(), keys.end(), [](int i, int j)
             { return abs(i) < abs(j); });
        vector<int> res;
        for (int x : keys)
        {
            if (c[x] > c[2 * x])
                return {};
            for (int i = 0; i < c[x]; ++i, c[2 * x]--)
                res.push_back(x);
        }
        return res;
    }
};
// @lc code=end