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 <= 1050 <= changed[i] <= 105
Solution 1: Multiset
Start from the smallest number x, erase one x * 2 from the set.
Time complexity: O(nlogn)
Space complexity: O(n)
C++/Multiset
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua class Solution { public: vector<int> findOriginalArray(vector<int>& changed) { if (changed.size() & 1) return {}; const int n = changed.size() / 2; multiset<int> s(begin(changed), end(changed)); while (ans.size() != n) { int o = *begin(s); s.erase(begin(s)); ans.push_back(o); auto it = s.find(o * 2); if (it == end(s)) return {}; s.erase(it); } return ans; } }; |
Solution 2: Hashtable
Time complexity: O(max(nums) + n)
Space complexity: O(max(nums))
C++/Hashtable
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: vector<int> findOriginalArray(vector<int>& changed) { if (changed.size() & 1) return {}; const int n = changed.size() / 2; const int kMax = *max_element(begin(changed), end(changed)); vector<int> m(kMax + 1); for (int x : changed) ++m[x]; if (m[0] & 1) return {}; vector<int> ans(m[0] / 2, 0); for (int x = 1; ans.size() != n; ++x) { if (x * 2 > kMax || m[x * 2] < m[x]) return {}; ans.insert(end(ans), m[x], x); m[x * 2] -= m[x]; } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment