题目描述
存在一个未知数组需要你进行还原，给你一个整数 n 表示该数组的长度。另给你一个数组 sums ，由未知数组中全部 2n 个 子集的和 组成（子集中的元素没有特定的顺序）。
返回一个长度为 n 的数组 ans 表示还原得到的未知数组。如果存在 多种 答案，只需返回其中 任意一个 。
如果可以由数组 arr 删除部分元素（也可能不删除或全删除）得到数组 sub ，那么数组 sub 就是数组 arr 的一个 子集 。sub 的元素之和就是 arr 的一个 子集的和 。一个空数组的元素之和为 0 。
注意：生成的测试用例将保证至少存在一个正确答案。
示例 1：
输入：n = 3, sums = [-3,-2,-1,0,0,1,2,3]
输出：[1,2,-3]
解释：[1,2,-3] 能够满足给出的子集的和：
- []：和是 0
- [1]：和是 1
- [2]：和是 2
- [1,2]：和是 3
- [-3]：和是 -3
- [1,-3]：和是 -2
- [2,-3]：和是 -1
- [1,2,-3]：和是 0
注意，[1,2,-3] 的任何排列和 [-1,-2,3] 的任何排列都会被视作正确答案。
示例 2：
输入：n = 2, sums = [0,0,0,0]
输出：[0,0]
解释：唯一的正确答案是 [0,0] 。
示例 3：
输入：n = 4, sums = [0,0,5,5,4,-1,4,9,9,-1,4,3,4,8,3,8]
输出：[0,-1,4,5]
解释：[0,-1,4,5] 能够满足给出的子集的和。
提示：
1 <= n <= 15sums.length == 2n-104 <= sums[i] <= 104
解法
方法一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | from sortedcontainers import SortedList
class Solution:
def recoverArray(self, n: int, sums: List[int]) -> List[int]:
m = -min(sums)
sl = SortedList(x + m for x in sums)
sl.remove(0)
ans = [sl[0]]
for i in range(1, n):
for j in range(1 << i):
if j >> (i - 1) & 1:
s = sum(ans[k] for k in range(i) if j >> k & 1)
sl.remove(s)
ans.append(sl[0])
for i in range(1 << n):
s = sum(ans[j] for j in range(n) if i >> j & 1)
if s == m:
for j in range(n):
if i >> j & 1:
ans[j] *= -1
break
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
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 | class Solution {
public int[] recoverArray(int n, int[] sums) {
int m = 1 << 30;
for (int x : sums) {
m = Math.min(m, x);
}
m = -m;
TreeMap<Integer, Integer> tm = new TreeMap<>();
for (int x : sums) {
tm.merge(x + m, 1, Integer::sum);
}
int[] ans = new int[n];
if (tm.merge(0, -1, Integer::sum) == 0) {
tm.remove(0);
}
ans[0] = tm.firstKey();
for (int i = 1; i < n; ++i) {
for (int j = 0; j < 1 << i; ++j) {
if ((j >> (i - 1) & 1) == 1) {
int s = 0;
for (int k = 0; k < i; ++k) {
if (((j >> k) & 1) == 1) {
s += ans[k];
}
}
if (tm.merge(s, -1, Integer::sum) == 0) {
tm.remove(s);
}
}
}
ans[i] = tm.firstKey();
}
for (int i = 0; i < 1 << n; ++i) {
int s = 0;
for (int j = 0; j < n; ++j) {
if (((i >> j) & 1) == 1) {
s += ans[j];
}
}
if (s == m) {
for (int j = 0; j < n; ++j) {
if (((i >> j) & 1) == 1) {
ans[j] *= -1;
}
}
break;
}
}
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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45 | class Solution {
public:
vector<int> recoverArray(int n, vector<int>& sums) {
int m = *min_element(sums.begin(), sums.end());
m = -m;
multiset<int> st;
for (int x : sums) {
st.insert(x + m);
}
st.erase(st.begin());
vector<int> ans;
ans.push_back(*st.begin());
for (int i = 1; i < n; ++i) {
for (int j = 0; j < 1 << i; ++j) {
if (j >> (i - 1) & 1) {
int s = 0;
for (int k = 0; k < i; ++k) {
if (j >> k & 1) {
s += ans[k];
}
}
st.erase(st.find(s));
}
}
ans.push_back(*st.begin());
}
for (int i = 0; i < 1 << n; ++i) {
int s = 0;
for (int j = 0; j < n; ++j) {
if (i >> j & 1) {
s += ans[j];
}
}
if (s == m) {
for (int j = 0; j < n; ++j) {
if (i >> j & 1) {
ans[j] = -ans[j];
}
}
break;
}
}
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
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 | func recoverArray(n int, sums []int) []int {
m := -slices.Min(sums)
rbt := redblacktree.NewWithIntComparator()
merge := func(key int, value int) {
if v, ok := rbt.Get(key); ok {
nxt := v.(int) + value
if nxt == 0 {
rbt.Remove(key)
} else {
rbt.Put(key, nxt)
}
} else {
rbt.Put(key, value)
}
}
for _, x := range sums {
merge(x+m, 1)
}
ans := make([]int, n)
merge(ans[0], -1)
ans[0] = rbt.Left().Key.(int)
for i := 1; i < n; i++ {
for j := 0; j < 1<<i; j++ {
if j>>(i-1)&1 == 1 {
s := 0
for k := 0; k < i; k++ {
if j>>k&1 == 1 {
s += ans[k]
}
}
merge(s, -1)
}
}
ans[i] = rbt.Left().Key.(int)
}
for i := 0; i < 1<<n; i++ {
s := 0
for j := 0; j < n; j++ {
if i>>j&1 == 1 {
s += ans[j]
}
}
if s == m {
for j := 0; j < n; j++ {
if i>>j&1 == 1 {
ans[j] = -ans[j]
}
}
break
}
}
return ans
}
|
方法二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution:
def recoverArray(self, n: int, sums: List[int]) -> List[int]:
sums.sort()
ans = []
for i in range(n, 0, -1):
k = 1 << i
d = sums[k - 1] - sums[k - 2]
cnt = Counter(sums[:k])
sums1, sums2 = [], []
sign = 1
for s in sums[:k]:
if not cnt[s]:
continue
cnt[s] -= 1
cnt[s + d] -= 1
sums1.append(s)
sums2.append(s + d)
if s + d == 0:
sign = -1
ans.append(sign * d)
sums = sums1 if sign == 1 else sums2
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
25
26
27
28
29
30
31
32
33 | class Solution {
public int[] recoverArray(int n, int[] sums) {
Arrays.sort(sums);
int[] sums1 = new int[1 << n];
int[] sums2 = new int[1 << n];
Map<Integer, Integer> cnt = new HashMap<>();
int[] ans = new int[n];
for (int i = n; i > 0; --i) {
int k = 1 << i;
int d = sums[k - 1] - sums[k - 2];
cnt.clear();
for (int j = 0; j < k; ++j) {
cnt.merge(sums[j], 1, Integer::sum);
}
int sign = 1;
for (int j = 0, p = 0; j < k; ++j) {
if (cnt.getOrDefault(sums[j], 0) == 0) {
continue;
}
cnt.merge(sums[j], -1, Integer::sum);
cnt.merge(sums[j] + d, -1, Integer::sum);
sums1[p] = sums[j];
sums2[p++] = sums[j] + d;
if (sums[j] + d == 0) {
sign = -1;
}
}
ans[i - 1] = sign * d;
System.arraycopy(sign == 1 ? sums1 : sums2, 0, sums, 0, k / 2);
}
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
25
26
27
28
29
30
31
32
33
34
35 | class Solution {
public:
vector<int> recoverArray(int n, vector<int>& sums) {
sort(sums.begin(), sums.end());
vector<int> ans(n);
unordered_map<int, int> cnt;
for (int i = n; i; --i) {
cnt.clear();
int k = 1 << i;
int d = sums[k - 1] - sums[k - 2];
for (int j = 0; j < k; ++j) {
cnt[sums[j]]++;
}
vector<int> sums1, sums2;
int sign = 1;
for (int j = 0; j < k; ++j) {
if (cnt[sums[j]] == 0) {
continue;
}
--cnt[sums[j]];
--cnt[sums[j] + d];
sums1.push_back(sums[j]);
sums2.push_back(sums[j] + d);
if (sums2.back() == 0) {
sign = -1;
}
}
ans[i - 1] = sign * d;
for (int j = 0; j < k / 2; ++j) {
sums[j] = sign == 1 ? sums1[j] : sums2[j];
}
}
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
25
26
27
28
29
30
31 | func recoverArray(n int, sums []int) (ans []int) {
sort.Ints(sums)
for i := n; i > 0; i-- {
k := 1 << i
d := sums[k-1] - sums[k-2]
cnt := map[int]int{}
for _, s := range sums[:k] {
cnt[s]++
}
sums1, sums2 := []int{}, []int{}
sign := 1
for _, s := range sums[:k] {
if cnt[s] == 0 {
continue
}
cnt[s]--
cnt[s+d]--
sums1 = append(sums1, s)
sums2 = append(sums2, s+d)
if s+d == 0 {
sign = -1
}
}
ans = append(ans, sign*d)
if sign == -1 {
sums1 = sums2
}
sums = sums1
}
return
}
|