class Solution {
public:
vector<int> recoverArray(int n, vector<int>& sums) {
}
};
1982. 从子集的和还原数组
存在一个未知数组需要你进行还原，给你一个整数 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原站题解
rust 解法, 执行用时: 472 ms, 内存消耗: 2.4 MB, 提交时间: 2023-10-10 23:32:04
impl Solution {
pub fn recover_array(n: i32, mut sums: Vec<i32>) -> Vec<i32> {
let mut res = Vec::new();
sums.sort_unstable();
for i in 1..=n {
let (d, mut l, mut r) = (sums[1] - sums[0], vec![0; sums.len() / 2], vec![0; sums.len() / 2]);
for j in 1..=l.len() {
let (u, v) = (sums.last().unwrap() - d, sums.pop().unwrap());
sums.remove(sums.binary_search(&u).unwrap());
l[r.len() - j] = u;
r[l.len() - j] = v;
}
res.push(if l.contains(&0) { d } else { -d });
std::mem::swap(&mut sums, if l.contains(&0) { &mut l } else { &mut r });
}
res
}
}
rust 解法, 执行用时: 48 ms, 内存消耗: 2.4 MB, 提交时间: 2023-10-10 23:31:52
impl Solution {
pub fn recover_array(n: i32, mut sums: Vec<i32>) -> Vec<i32> {
let mut res = Vec::new();
sums.sort_unstable();
let len = sums.len();
let mut sums2 = vec![0; len / 2];
let mut vis = vec![false; len];
for i in 0..n {
let sz = len >> i;
for j in 0..sz { vis[j] = false; }
let (mut p1, mut pos, cand) = (0, 0, sums[1] - sums[0]);
for j in 0..sz {
if vis[j] { continue; }
pos = usize::max(pos, j) + 1;
let targ = sums[j] + cand;
while sums[pos] != targ { pos += 1; }
vis[pos] = true;
sums[p1] = sums[j];
sums2[p1] = sums[pos];
p1 += 1;
}
let flg = sums[0..sz / 2].contains(&0);
if !flg { std::mem::swap(&mut sums, &mut sums2); }
res.push(if flg { cand } else { -cand });
}
res
}
}
java 解法, 执行用时: 62 ms, 内存消耗: 53 MB, 提交时间: 2023-10-10 23:31:03
class Solution {
public static int[] recoverArray(int n, int[] sums) {
Arrays.sort(sums);
int[] ans = new int[n];
int cur = 0;
for (int i = n; i >= 2; --i) {
int d = sums[1] - sums[0];
int left = 0, right = 0;
int[] s = new int[1 << (i - 1)];
int[] t = new int[1 << (i - 1)];
int si = 0, ti = 0;
boolean flag = false;
boolean[] used = new boolean[1 << i];
while (true) {
while (left < (1 << i) && used[left]) {
++left;
}
if (left == 1 << i) {
break;
}
s[si++] = sums[left];
if (sums[left] == 0) {
flag = true;
}
used[left] = true;
while (used[right] || sums[right] != sums[left] + d) {
++right;
}
t[ti++] = sums[right];
used[right] = true;
}
if (flag) {
ans[cur++] = d;
sums = s;
} else {
ans[cur++] = -d;
sums = t;
}
}
ans[cur++] = sums[0] + sums[1];
return ans;
}
}
cpp 解法, 执行用时: 204 ms, 内存消耗: 108.5 MB, 提交时间: 2023-10-10 23:30:29
class Solution {
public:
vector<int> recoverArray(int n, vector<int>& sums) {
// 提前将数组排好序
sort(sums.begin(), sums.end());
vector<int> ans;
for (int i = n; i >= 2; --i) {
int d = sums[1] - sums[0];
// 双指针构造 s 和 t
int left = 0, right = 0;
vector<int> s, t;
// 记录每个子集和是否选过
vector<int> used(1 << i);
while (true) {
// left 指针找到最小的未被选择过的子集和
while (left < (1 << i) && used[left]) {
++left;
}
if (left == (1 << i)) {
break;
}
s.push_back(sums[left]);
used[left] = true;
// right 指针找到 sums[left] + d
while (used[right] || sums[right] != sums[left] + d) {
++right;
}
t.push_back(sums[right]);
used[right] = true;
}
if (find(s.begin(), s.end(), 0) != s.end()) {
// 包含 d 并求解 (n-1, s)
ans.push_back(d);
sums = move(s);
}
else {
// 包含 -d 并求解 (n-1, t)
ans.push_back(-d);
sums = move(t);
}
}
// 迭代到 n=1 时，数组中必然一个为 0，另一个为剩下的最后一个数
ans.push_back(sums[0] + sums[1]);
return ans;
}
};
python3 解法, 执行用时: 728 ms, 内存消耗: 22.5 MB, 提交时间: 2023-10-10 23:30:15
class Solution:
def recoverArray(self, n: int, sums):
# 提前将数组排好序
sums.sort()
ans = list()
for i in range(n, 1, -1):
d = sums[1] - sums[0]
# 双指针构造 s 和 t
left = right = 0
s, t = list(), list()
# 记录每个子集和是否选过
used = set()
while True:
# left 指针找到最小的未被选择过的子集和
while left < (1 << i) and left in used:
left += 1
if left == (1 << i):
break
s.append(sums[left])
used.add(left)
# right 指针找到 sums[left] + d
while right in used or sums[right] != sums[left] + d:
right += 1
t.append(sums[right])
used.add(right)
if 0 in s:
# 包含 d 并求解 (n-1, s)
ans.append(d)
sums = s
else:
# 包含 -d 并求解 (n-1, t)
ans.append(-d)
sums = t
# 迭代到 n=1 时，数组中必然一个为 0，另一个为剩下的最后一个数
ans.append(sums[0] + sums[1])
return ans
python3 解法, 执行用时: 1196 ms, 内存消耗: 24.5 MB, 提交时间: 2023-10-10 23:30:01
class Solution:
def recoverArray(self, n: int, sums):
# n 个数构成程度为 2^n 的子集和数组 sums
# 返回值为空表示无解，否则表示有解
def dfs(n: int, sums: List[int]) -> List[int]:
# 递归到 n=1 时，数组中必然一个为 0，另一个为剩下的最后一个数
# 如果满足该要求，返回剩下的最后一个数，否则返回表示无解的空数组
if n == 1:
if sums[0] == 0:
return [sums[1]]
if sums[1] == 0:
return [sums[0]]
return []
d = sums[1] - sums[0]
# 双指针构造 s 和 t
left = right = 0
s, t = list(), list()
# 记录每个子集和是否选过
used = set()
while True:
# left 指针找到最小的未被选择过的子集和
while left < (1 << n) and left in used:
left += 1
if left == (1 << n):
break
s.append(sums[left])
used.add(left)
# right 指针找到 sums[left] + d
while right in used or sums[right] != sums[left] + d:
right += 1
t.append(sums[right])
used.add(right)
# 尝试包含 d 并递归求解 (n-1, s)
ans = dfs(n - 1, s)
if ans:
return ans + [d]
# 尝试包含 -d 并递归求解 (n-1, t)
ans = dfs(n - 1, t)
if ans:
return ans + [-d]
# 无解返回空数组
return []
# 提前将数组排好序
sums.sort()
return dfs(n, sums)
cpp 解法, 执行用时: 384 ms, 内存消耗: 151.8 MB, 提交时间: 2023-10-10 23:29:49
class Solution {
private:
// n 个数构成程度为 2^n 的子集和数组 sums
// 返回值为空表示无解，否则表示有解
vector<int> dfs(int n, vector<int>& sums) {
// 递归到 n=1 时，数组中必然一个为 0，另一个为剩下的最后一个数
// 如果满足该要求，返回剩下的最后一个数，否则返回表示无解的空数组
if (n == 1) {
if (sums[0] == 0) {
return {sums[1]};
}
if (sums[1] == 0) {
return {sums[0]};
}
return {};
}
int d = sums[1] - sums[0];
// 双指针构造 s 和 t
int left = 0, right = 0;
vector<int> s, t;
// 记录每个子集和是否选过
vector<int> used(1 << n);
while (true) {
// left 指针找到最小的未被选择过的子集和
while (left < (1 << n) && used[left]) {
++left;
}
if (left == (1 << n)) {
break;
}
s.push_back(sums[left]);
used[left] = true;
// right 指针找到 sums[left] + d
while (used[right] || sums[right] != sums[left] + d) {
++right;
}
t.push_back(sums[right]);
used[right] = true;
}
// 尝试包含 d 并递归求解 (n-1, s)
vector<int> ans = dfs(n - 1, s);
if (!ans.empty()) {
ans.push_back(d);
return ans;
}
// 尝试包含 -d 并递归求解 (n-1, t)
ans = dfs(n - 1, t);
if (!ans.empty()) {
ans.push_back(-d);
return ans;
}
// 无解返回空数组
return {};
}
public:
vector<int> recoverArray(int n, vector<int>& sums) {
// 提前将数组排好序
sort(sums.begin(), sums.end());
return dfs(n, sums);
}
};