我看到这个问题在一个编程面试博客上。
如果按非递减顺序给出
n个数的配对和，请确定这些单独的数字。 如果总和出现错误，请打印-1。
示例：
i/p: 4 5 7 10 12 13
o/p: 1 3 4 9
6个回答
11
设B是由两两相加得到的列表，使得B[0] <= B[1] <= ... <= B[m-1]，A是我们要查找的原始数字列表，其中有n个数字，且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]，然后从B中删除A[1] + A[2]。接下来最小的元素一定是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
- PengOne
13
谢谢 Pengone。我正在尝试理解你的解决方案。那么，为了找到 A[0]，我们必须尝试在 0 和 B[0]/2 之间的每个值，当我们继续算法并发现没有正确的解决方案时，我们就知道它不正确了，对吗？或者我漏掉了什么东西吗？ - ash
@ash 是的。我刚刚添加了一些示例，希望能有所帮助。如果还不清楚，请告诉我。 - PengOne
再次感谢Pengone。我明白了，这是一个合理的方法。但我仍然想知道，如果第一个和非常大，我们是否需要通过算法进行多次迭代才能找到A [0]。我在想，如果我们使用某种二进制搜索方法，如果一次减法给出负值，那么A [0]应该小于那个值，以此类推...这有意义吗？ - ash
2如果我们知道A [0]，那么我们可以从A的每个值中减去它，并且从B中减去两次它。这是完全等效的。然后，因为A [0]为0，我们知道B包括A的每个元素（当然除了第一个0）。这有帮助吗？ - Aaron McDaid
1@AaronMcDaid 这是ash的想法。我不确定那样会起作用。而且，正如Ted指出的那样，
B[0]/2-1可能远大于n，所以即使在那里进行二分查找，也可能比O(n)更糟糕。 - PengOne显示剩余8条评论
1
一些提示：
输入的大小为N *（N-1）/ 2，因此您可以推断出输出的大小（即输入中的6个元素对应于输出中的4个元素）
输入的总和是输出总和除以
N-1（即1 + 3 + 4 + 9 =（4 + 5 + 7 + 10 + 12 + 13）/（4-1））最低的输入和最高的输入分别是两个最低输出和两个最高输出的总和（即
4 = 1 + 3和13 = 4 + 9）下一个最低的输入（5）与第一个（1）仅相差一个加数，因此您可以通过取差（5-1）来计算其中一个加数。
- Raymond Hettinger
1
1我无法想象如何使用a+b+c+d=something，a+b=something和c+d=something来解决a的值...或者我在你的第四个提示中漏掉了什么... - ash
1
PengOne的方法可以恢复给定的A[0]和B，但是有一种更好的方法来计算A[0]。请注意，B的两个最小元素为：
对于某些i，我们只需要尝试O(n^{1/2})种可能性，因为i受到O(n^{1/2})的限制，并查看是否有一种有效的设置剩余元素A的方法，根据PengOne的解决方案。总运行时间为O(n^{3/2})，其中n是输入中数字的数量。
B[0] = A[0] + A[1]
B[1] = A[0] + A[2]
并且
B[i] = A[1] + A[2]
对于某些 i。
因此，
A[0] = (B[0] + B[1] - B[i]) / 2
对于某些i，我们只需要尝试O(n^{1/2})种可能性，因为i受到O(n^{1/2})的限制，并查看是否有一种有效的设置剩余元素A的方法，根据PengOne的解决方案。总运行时间为O(n^{3/2})，其中n是输入中数字的数量。
- jonderry
1
我认为Ferdinand Beyer在删除他的答案之前是正确的。重复他的一部分方法：你有四个未知数，a、b、c和d，其中a ≤ b ≤ c ≤ d。基于此，可以形成所有和的部分排序：
a + b ≤ a + c
a + b ≤ a + d
a + c ≤ b + c
a + d ≤ b + d
a + d ≤ c + d
b + c ≤ b + d
b + d ≤ c + d
如果这是一个完全有序的集合，那么每个六个值 a + b, a + c, a + d, b + c, b + d, 和 c + d 都是已知的。然后可以按照 Ferdinand 的原始计划轻松解决联立方程。
不幸的是，存在一对（a + d，b + c）可以以任意顺序排序。但这很容易处理：假设 a + d < b + c（输入值都是不同的，所以不必担心使用 ≤），并尝试解决联立方程。然后假设 b + c < a + d 并重复。如果两组方程都有解，则原问题有两个答案。如果两组方程都没有解，则输出应为 -1。否则，您就有了（唯一的）解决方案。
- Ted Hopp
11
抱歉，但输入顺序是非递减的，所以它们可能不是不同的，对吧？如果输入是一个更大的数字，意味着原始数字集更多，那么部分有序对的数量就会增加，对吧？我还在思考，但你的解决方案对我来说很明显。 - ash
2@ash - 我的错误；我是根据你给出的具体数字进行工作的。但是没有什么损失。只需假设
a + d ≤ b + c，反之亦然。唯一的复杂性是微不足道的：两个解的情况可能会合并为一个解。 - Ted Hopp@ash - 如果输入包含重复数字，当两个成对和相等时，您总是知道输出中需要有多少个数字。处理更长的输入变得更加复杂，但可以以类似的方式处理：确定部分排序，然后研究每个兼容的总排序以找到解决方案。计算数量增加了，但配方仍然很简单。 - Ted Hopp
我正在尝试解决你的六个大小数组的问题。a+b，a+c，a+d，a+e，a+f，b+c，b+d，b+e，b+f，c+d，c+e，c+f，e+f。正如你所说，第一个元素总是a+b。第二个元素总是a+c。现在对于第三个元素，它可以是b+c或a+d。到目前为止还好。
现在我们有另一个不等式。b+c，a+e这意味着它可能是a+d b+c a+e或a+d a+e b+c或b+c a+d a+e或b+c a+d b+d a+e等等。然后是c+d，它与a+d没有顺序关系。 - ash
1@TedHopp 我提供了一个多项式时间的解决方案，因此只有当P=NP时，这个问题才是NP难的。 - PengOne
显示剩余6条评论
0
最近我在查看面试题，并在@PengOne的提示下解决了找到第一个值的问题。
因此，如果有人需要完整的工作解决方案： 它是用PHP编写的：
时间复杂度：O（（n *（n-2））+ 3 + n），带有辅助变量。 空间复杂度：几乎与时间复杂度相同。
<?php
function getSublistSize($length)
{
$i = 2;
$n = 0;
while ($i <= $length) {
if (is_int($length / $i)) {
if ($length == $i * ($i + 1) / 2) {
return ($i + 1);
}
}
++$i;
}
return $n;
}
function findSubstractList(array $list)
{
$length = count($list);
$n = getSublistSize($length);
$nth = $n - 1;
$substractList = [];
$substractTotal = array_sum($list) / ($length / 2); // A + B + C + D
/**
* formula : A = (list[0] + list[1] - list[nth -1]) / 2
* list[0] = A + B,
* list[1] = A + C,
* list[nth - 1] = B + C
*
* => ((A + B) + (A + C) - (B + C)) / 2
* => (A + A + (B + C - B - C)) / 2
* => (2A + 0) / 2 => 2A / 2
* => A
*/
$substractList[] = (($list[0] + $list[1]) - $list[$nth]) / 2;
for ($i = 0; $i < $nth; ++$i) {
$substractList[] = ($list[$i] - $substractList[0]);
}
// $substractList[3] = $substractTotal - ($list[$nth - 1] + $substractList[0]);
return $substractList;
}
$list = [5, 8, 14, 28, 40, 11, 17, 31, 43, 20, 34, 46, 40, 52, 66];
print_r(findSubstractList($list));
/**
* P ) [6, 11, 101, 15, 105, 110];
* S ) [1, 5, 10, 100]
*
* P ) [5, 8, 14, 28, 40, 11, 17, 31, 43, 20, 34, 46, 40, 52, 66];
* S ) [1, 4, 7, 13, 27, 39]
*
*/
- FZE
-2
我不确定最快的算法，但我可以解释这是如何工作的。
输出的第一个数字是第一个输入和第二个输入之间的差异。
5-4=1
所以现在你有了第一个输出数字。
输出的第二个数字是第一个输入数字减去第一个输出数字。
4-1=3
输出的第三个值是第二个输出值减去第一个输入值。
5-1=4
- Isaac Fife
2
2第一个数字不是5-4=1，实际上5-4是“第三个数字 - 第二个数字”。 - Saeed Amiri
什么？5 是从 1+4 生成的。 - Isaac Fife
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接