05 August 2008
一个数组的每个元素元素变为二倍，然后接在原数组后，打乱顺序，叫double array，给一个数组返回变化前的样子，如果不能返回则返回空
步骤
Count all numbers.
Loop all numbers on the order of its absolute.
We have counter[x] of x, so we need the same amount of 2x wo match them.
If c[x] > c[2 * x], then we return []
If c[x] <= c[2 * x], then we repeatly do c[2 * x]– and append 2x to result res
Don’t worry about 0, it doesn’t fit the logic above but it won’t break our algorithme.
In case count[0] is odd, it won’t get matched in the end.
In case count[0] is even, we still have c[0] <= c[2 * 0].
And we still need to check all other numbers.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] findOriginalArray(int[] A) {
int n = A.length, i = 0;
if (n % 2 == 1) return new int[0];
int[] res = new int[n / 2];
Map<Integer, Integer> count = new TreeMap<>();
for (int a : A)
count.put(a, count.getOrDefault(a, 0) + 1);
for (int x : count.keySet()) {
if (count.get(x) > count.getOrDefault(x + x, 0))
return new int[0];
for (int j = 0; j < count.get(x); ++j) {
res[i++] = x;
count.put(x + x, count.get(x + x) - 1);
}
}
return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int[] findOriginalArray(int[] changed) {
if (changed.length % 2 != 0) return new int[]{};
Arrays.sort(changed);
int[] map = new int[100001], original = new int[changed.length / 2];
int i = 0;
for (int num: changed) {
map[num]++;
}
for (int num: changed) {
if (map[num] > 0) {
map[num]--;
original[i++] = num;
if (num > 50000 || map[num + num] == 0) return new int[]{};
map[num + num]--;
}
}
return original;
}
不用排序
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
class Solution {
public int[] findOriginalArray(int[] changed) {
if(changed.length%2!=0) return new int[0];
int mid = changed.length/2;
int[] res = new int[mid];
int[] freq = new int[100001];
for(int no : changed)
freq[no]++;
int idx=0;
for(int no=0; no<freq.length; no++){
while(freq[no] > 0 && no*2 < 100001 && freq[no*2]>0){
freq[no]--;
freq[no*2]--;
res[idx++] = no;
}
}
for(int i=0; i<freq.length; i++){
if(freq[i]!=0) return new int[0];
}
return res;
}
}