第 255 场周赛 5853. 从子集的和还原数组
Rank 205,手速慢了。最后一题不会做。。。
Desciption
存在一个未知数组需要你进行还原,给你一个整数 n 表示该数组的长度。另给你一个数组 sums ,由未知数组中全部 2n 个 子集的和组成(子集中的元素没有特定的顺序)。
返回一个长度为 n 的数组 ans 表示还原得到的未知数组。如果存在 多种答案,只需返回其中 任意一个。
如果可以由数组 arr 删除部分元素(也可能不删除或全删除)得到数组 sub ,那么数组 sub 就是数组 arr 的一个 子集。sub 的元素之和就是 arr 的一个 子集的和。一个空数组的元素之和为 0 。
注意: 生成的测试用例将保证至少存在一个正确答案
1 <= n <= 15
sums.length == 2^n
-10^4 <= sums[i] <= 10^4
示例:
输入: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] 能够满足给出的子集的和。
Solution
这个题在比赛的时候没有想出来,记录一下当时的思路
- 观察一下样例,比较容易看出来的是,sums里面的最大值肯定是所有正整数的和(如果没有正整数,最大值为空集的和 0),最小值是所有负整数的和(如果没有负整数,最小值为空集的和 0)
- 题目里给的 n 比较小,2^n 也才 3w+,考虑暴力的做法
- 怎么样求出数组里的数呢,有一个比较简单的想法:对 sums 数组进行排序,如果最小值 sums[0] 为 0,则其中有一个数肯定是 sums[1];如果最大值 sum[len-1] 为 0,则其中有一个数肯定是 sums[len-2];
如果最小值 < 0,最大值 > 0,则有一个数为 sum[0] - sum[1], 另外一个数为 sum[len-1] - sum[len-2] (这个结论是错误的) - 知道其中一些数后,则把这些数组成的集合的和,从 sums 数组中进行删除,进行下一轮迭代。 这样做的代码复杂度有点高,考虑到 n 不是很大,还是尝试这样写了一下,结果样例都没过就比赛结束了
看了一下题解,我的分析方法应该是对的,但是有两个地方我想错
- 我们已经知道:sums里面的最大值肯定是所有正整数的和(如果没有正整数,最大值为空集的和 0)。那思考一下,次大值是怎么来的?次大值可能是(最大值 - 原数组里最小的非负整数)or (最大值 + 原数组里最大的负整数),也就是说,我们用 最大值 - 次大值 得到的结果是原数组里某一个数的绝对值
- 假设这个数是一个 非负整数 x,我们该怎么过滤掉所有包含这个 x 的集合呢?首先最小值肯定是不会包含这个 x 的,因此我们就可以知道 最小值+x 可以被过滤掉。进而思考到如果把 最小值+x 放到队列里,再从小到大遍历 sums 数组,如果 sums[i] 出现在队列里,说明 sums[i] 包含了 x,否则就把 sums[i]+x 放到队列里。这样就过滤掉所有包含 x 的集合。如果 x 是负数,则从大到小遍历一遍
- 这样我们就可以得到不包含 x 的所有的集合的和,假设为 sub_sums,就又可以从第一步开始处理。由于我们只知道某一个数 x 的绝对值,因此我们需要把非负整数 和 负整数的场景都试一下,然后递归处理。复杂度(n * 2^n)
- 递归的停止条件是,sub_sums 的大小为2,即集合内只有一个数的场景,这时 sub_sums[0] 和 sum_sums[1] 肯定有一个为0,另外一个数则是数组里的数
Code
class Solution {
public int[] recoverArray(int n, int[] sums) {
Arrays.sort(sums);
int len = sums.length;
int[] ans = new int[n];
if (n == 1) {
ans[0] = sums[0] == 0 ? sums[1] : sums[0];
return ans;
}
dfs(sums, ans, len, 0);
return ans;
}
public boolean dfs(int[] sums, int[] ans, int len, int dep) {
if (len == 2) {
if (sums[1] != 0 && sums[0] != 0) {
return false;
}
int x = sums[1] - sums[0];
if (sums[1] == 0) {
ans[dep] = -x;
} else {
ans[dep] = x;
}
return true;
}
int sub_len = len / 2;
int[] new_sums = new int[sub_len];
int x = sums[len - 1] - sums[len - 2];
// x is abs(ans[dep]), if ans[dep] > 0
Queue<Integer> q = new LinkedList<>();
int cnt = 0;
for (int i = 0; i < len; ++i) {
if (q.isEmpty() || q.peek() != sums[i]) {
q.add(sums[i] + x);
if (cnt < sub_len) {
new_sums[cnt++] = sums[i];
} else {
cnt++;
}
} else {
q.poll();
}
}
if (cnt == sub_len) {
ans[dep] = x;
if (dfs(new_sums, ans, sub_len, dep + 1)) {
return true;
}
}
// x is abs(ans[dep]), if ans[dep] < 0
q.clear();
cnt = sub_len - 1;
for (int i = len - 1; i >= 0; --i) {
if (q.isEmpty() || q.peek() != sums[i]) {
q.add(sums[i] - x);
if (cnt >= 0) {
new_sums[cnt--] = sums[i];
} else {
cnt--;
}
} else {
q.poll();
}
}
if (cnt == -1) {
ans[dep] = -x;
if (dfs(new_sums, ans, sub_len, dep + 1)) {
return true;
}
}
return false;
}
}