有效地获取排序列表的排序总和

Question

您有一个升序的数字列表,您可以想到的最有效的算法是获取该列表中每两个数字的总和的升序列表.结果列表中的重复项无关紧要,如果您愿意,可以删除它们或避免使用它们.

要清楚,我对算法很感兴趣.您可以随意使用您喜欢的任何语言和范例发布代码.

Answer 1

编辑截至2018年:您可能应该停止阅读此内容.(但我不能删除它,因为它被接受.)

如果你写出这样的总和:

1 4  5  6  8  9
---------------
2 5  6  7  9 10
  8  9 10 12 13
    10 11 13 14
       12 14 15
          16 17
             18

你会注意到,因为M [i,j] <= M [i,j + 1]和M [i,j] <= M [i + 1,j],那么你只需要检查左上角"角落"并选择最低的角落.

例如

当然,当你有很多左上角时,这个解决方案就会变成现实.

我很确定这个问题是Ω(n²),因为你必须计算每个M [i,j]的总和 - 除非有人有更好的求和算法:)

您可以通过在优先级队列中的每一行中存储第一个未删除的条目,在O(n ^ 2 log n)时间内实现此算法,但渐渐地,这并不比仅生成所有求和和排序更好. (2认同)