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 <= 1050 <= changed[i] <= 105
Solutions#
Solution 1: Sorting + Counting + Traversal#
First, we check if the length $n$ of the array changed is odd. If it is, we directly return an empty array.
Then, we sort the array changed, and use a hash table or array cnt to count the occurrence of each element in changed.
Next, we traverse the array changed. For each element $x$ in changed, we first check if $x$ exists in the hash table cnt. If it does not exist, we directly skip this element. Otherwise, we check if $x \times 2$ exists in cnt. If it does not exist, we directly return an empty array. Otherwise, we add $x$ to the answer array ans, and decrease the occurrence counts of $x$ and $x \times 2$ in cnt by $1$ each.
After the traversal, we check if the length of the answer array ans is $\frac{n}{2}$. If it is, we return ans, otherwise we return an empty array.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array changed.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution:
def findOriginalArray(self, changed: List[int]) -> List[int]:
n = len(changed)
if n & 1:
return []
cnt = Counter(changed)
changed.sort()
ans = []
for x in changed:
if cnt[x] == 0:
continue
if cnt[x * 2] <= 0:
return []
ans.append(x)
cnt[x] -= 1
cnt[x * 2] -= 1
return ans if len(ans) == n // 2 else []
|
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
| class Solution {
public int[] findOriginalArray(int[] changed) {
int n = changed.length;
if (n % 2 == 1) {
return new int[] {};
}
Arrays.sort(changed);
int[] cnt = new int[changed[n - 1] + 1];
for (int x : changed) {
++cnt[x];
}
int[] ans = new int[n / 2];
int i = 0;
for (int x : changed) {
if (cnt[x] == 0) {
continue;
}
if (x * 2 >= cnt.length || cnt[x * 2] <= 0) {
return new int[] {};
}
ans[i++] = x;
cnt[x]--;
cnt[x * 2]--;
}
return i == n / 2 ? ans : new int[] {};
}
}
|
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
| class Solution {
public:
vector<int> findOriginalArray(vector<int>& changed) {
int n = changed.size();
if (n & 1) {
return {};
}
sort(changed.begin(), changed.end());
vector<int> cnt(changed.back() + 1);
for (int& x : changed) {
++cnt[x];
}
vector<int> ans;
for (int& x : changed) {
if (cnt[x] == 0) {
continue;
}
if (x * 2 >= cnt.size() || cnt[x * 2] <= 0) {
return {};
}
ans.push_back(x);
--cnt[x];
--cnt[x * 2];
}
return ans.size() == n / 2 ? ans : vector<int>();
}
};
|
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
| func findOriginalArray(changed []int) []int {
n := len(changed)
ans := []int{}
if n&1 == 1 {
return ans
}
sort.Ints(changed)
cnt := make([]int, changed[n-1]+1)
for _, x := range changed {
cnt[x]++
}
for _, x := range changed {
if cnt[x] == 0 {
continue
}
if x*2 >= len(cnt) || cnt[x*2] <= 0 {
return []int{}
}
ans = append(ans, x)
cnt[x]--
cnt[x*2]--
}
if len(ans) != n/2 {
return []int{}
}
return 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
| function findOriginalArray(changed: number[]): number[] {
const n = changed.length;
if (n & 1) {
return [];
}
const cnt = new Map<number, number>();
for (const x of changed) {
cnt.set(x, (cnt.get(x) || 0) + 1);
}
changed.sort((a, b) => a - b);
const ans: number[] = [];
for (const x of changed) {
if (cnt.get(x) == 0) {
continue;
}
if ((cnt.get(x * 2) || 0) <= 0) {
return [];
}
ans.push(x);
cnt.set(x, (cnt.get(x) || 0) - 1);
cnt.set(x * 2, (cnt.get(x * 2) || 0) - 1);
}
return ans.length == n / 2 ? ans : [];
}
|
