首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >从所有子集恢复原始阵列

从所有子集恢复原始阵列
EN

Stack Overflow用户
提问于 2018-06-03 13:28:40
回答 2查看 1.2K关注 0票数 4

你会得到一个数组的所有子集和。然后,您应该从提供的子集和中恢复原始数组。

保证原始数组中的每个元素都是非负数且小于10^5。原始数组中的元素不超过20个。原始数组也会被排序。保证输入是有效的。

示例1

如果提供的子集和如下所示:

代码语言:javascript
复制
0 1 5 6 6 7 11 12

我们可以快速推断出原始数组的大小为3,因为有8 (2^3)个子集。上述输入的输出(即原始数组)如下所示:

代码语言:javascript
复制
1 5 6

示例2

输入:

代码语言:javascript
复制
0 1 1 2 8 9 9 10

输出:

代码语言:javascript
复制
1 1 8

我尝试了什么

由于保证所有元素都是非负的,因此输入中的最大整数必须是数组的总和。然而,我不确定我该如何从那里开始。从逻辑上讲,我认为下一个(2^2 - 1)个最大的子集和必须包括数组中除一个元素之外的所有元素。

但是,当原始数组为以下数组时,上述逻辑不起作用:

代码语言:javascript
复制
1 1 8

这就是为什么我被困住了,不知道如何继续下去。

EN

回答 2

Stack Overflow用户

发布于 2018-06-03 14:22:44

假设S是子集和数组,A是原始数组。我假设S是经过排序的。

代码语言:javascript
复制
|A| = log2(|S|)
S[0] = 0
S[1] = A[0]
S[2] = A[1]
S[3] = EITHER A[2] OR A[0] + A[1].

一般来说,I >= 3的Si可以是A的一个元素,也可以是您已经遇到的A的元素的组合。在处理S时,每跳过一次生成给定数字的A的已知元素的组合,将任何剩余的数字添加到A中。当A达到正确的大小时停止。

例如,如果为A=1,2,7,8,9,则S将包括1,2,1+2=3、...,1+8=9、2+7=9,9、....在处理S时,由于1+8和2+7,我们跳过两个9,然后看到第三个9,我们知道它肯定属于A。

例如,如果S=0,1,1,2,8,9,9,10,那么我们知道A有3个元素,A的前2个元素是1,1,当我们得到2时,我们跳过它,因为1+1=2,我们附加8,我们完成了,因为我们有3个元素。

票数 3
EN

Stack Overflow用户

发布于 2018-06-05 06:23:49

这里有一个简单的算法,不需要找出哪个子集和给定的数字。

S←输入序列

X←空序列

而S有一个非零元素:

  1. d当S不为空时,
  2. Insert d in X
  3. N

empty sequence

  1. in X
  2. N

empty sequence

  1. :H19z←S的最小元素H111从S中删除z和z+d (如果S不包含z+d,则是错误的;如果several).
    • Insert z在N.

中,则仅删除z和z+d的一个实例

  1. S

N←

输出X。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/50663548

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档