以非递增顺序的n个数的成对和

Question

我在编程访谈博客中看到了这个问题.

如果n以非递减顺序给出成对的数字和,则识别各个数字.如果总和已损坏打印-1.

例:

i/p: 4 5 7 10 12 13 

o/p: 1 3 4 9

提示就足够了.

Answer 1

让B是两两和的名单,B[0] <= B[1] <= ... <= B[m-1]并让A是我们正在试图找到,用数字的原始列表A[0] < A[1] < ... < A[n-1],其中m = n(n-1)/2.

给定A[0],计算A多项式时间

A从最小元素到最大元素构建.假设我们已经知道了A[0].然后,因为B[0]是最小的元素B,它只能出现A[0] + A[1].同样,B[1]必须相等A[0] + A[2].因此,如果我们知道A[0],我们可以计算A[1]和A[2].

然而,在那之后,这种模式崩溃了.B[2]既可以是A[0] + A[3]或A[1] + A[2],没有先验知识,我们无法知道它是哪一个.但是,如果我们知道A[0],我们可以计算A[1]并A[2]如上所述,然后A[1] + A[2]从中删除B.然后保证下一个最小的元素A[0] + A[3],这使我们能够找到A[3].继续这样,我们可以找到所有A没有回溯的东西.算法看起来像这样:

for i from 1 to n-1 {
    // REMOVE SEEN SUMS FROM B
    for j from 0 to i-2 {
        remove A[j]+A[i-1] from B
    }
    // SOLVE FOR NEXT TERM
    A[i] = B[0] - A[0]
}
return A

以下是您的示例的工作原理,B = [4,5,7,10,12,13]如果我们知道A[0]=1:

start
    B = [4,5,7,10,12,13]
    A[0] = 1

i=1: 
    B = [4,5,7,10,12,13]
    A[1] = 4-1 = 3

i=2:
    Remove 1+3 from B
    B = [5,7,10,12,13]
    A[2] = 5-1 = 4

i=3:
    Remove 1+4 and 3+4 from B
    B = [10,12,13]
    A[3] = 10-1 = 9

end
    Remove 1+9 and 3+9 and 4+9 from B
    B = []
    A = [1,3,4,9]

所以这一切都归结为知道A[0],我们可以从中计算其余部分A.

A[0]在多项式时间内计算

我们现在可以简单地尝试各种可能性A[0].因为我们知道B[0] = A[0] + A[1],我们知道A[0]必须是0和之间的整数B[0]/2 - 1.我们也知道

B[0] = A[0] + A[1]
B[1] = A[0] + A[2]

此外,还有一些索引i与2 <= i <= n-1使得

B[i] = A[1] + A[2]

为什么？因为唯一的条目可能小于A[1]+A[2]形式A[0] + A[j],并且最多只有n-1这样的表达式.因此我们也知道

A[0] = (B[0]+B[1] - B[i])/2

对于一些2 <= i <= n-1.这与A[0]介于两者之间的事实0以及B[0]/2-1仅提供几种A[0]测试可能性的事实相结合.

例如,有两种可能性A[0]:0或1.如果我们尝试算法A[0]=0,这是发生的事情:

start
    B = [4,5,7,10,12,13]
    A[0] = 0

i=1: 
    B = [4,5,7,10,12,13]
    A[1] = 4-0 = 4

i=2:
    Remove 0+4 from B
    B = [5,7,10,12,13]
    A[2] = 5-0 = 5

i=3:
    Remove 0+5 and 4+5 from B
    B = !!! PROBLEM, THERE IS NO 9 IN B!

end