2007. Find Original Array From Doubled Array
Description
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
Solutions
Solution 1: Sorting
We notice that if the array changed
is a double array, then the smallest element in the array changed
must also be an element in the original array. Therefore, we can first sort the array changed
, and then start from the first element to traverse the array changed
in ascending order.
We use a hash table or array $cnt$ to count the occurrence of each element in the array changed
. For each element $x$ in the array changed
, we first check whether $x$ exists in $cnt$. If it does not exist, we skip this element. Otherwise, we subtract one from $cnt[x]$, and check whether $x \times 2$ exists in $cnt$. If it does not exist, we return an empty array directly. Otherwise, we subtract one from $cnt[x \times 2]$, and add $x$ to the answer array.
After the traversal, we return the answer array.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$, where $n$ is the length of the array changed
.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|