有效地获取已排序列表的已排序总和 [英] Efficiently get sorted sums of a sorted list

问题描述

您有一个递增的数字列表，您可以想到哪种最有效的算法来获得该列表中每两个数字之和的递增列表.结果列表中的重复项无关紧要，您可以删除它们，也可以根据需要避免.

You have an ascending list of numbers, what is the most efficient algorithm you can think of to get the ascending list of sums of every two numbers in that list. Duplicates in the resulting list are irrelevant, you can remove them or avoid them if you like.

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

To be clear, I'm interested in the algorithm. Feel free to post code in any language and paradigm that you like.

推荐答案

截至2018年您可能应该停止阅读此内容. (但是我无法删除它，因为它已被接受.)

Edit as of 2018: You should probably stop reading this. (But I can't delete it as it is accepted.)

如果您这样写出总和:

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]，所以您只需要检查左上方的角"，然后选择最低的角".

You'll notice that since M[i,j] <= M[i,j+1] and M[i,j] <= M[i+1,j], then you only need to examine the top left "corners" and choose the lowest one.

例如

• 仅在左上角1个，选择2个
• 仅1个，选择5个
• 6或8，选择6
• 7或8，选择7
• 9或8，选择8
• 9或9，同时选择两个:)
• 10或10或10，全选
• 12或11，选择11
• 12或12，都选择
• 13或13，都选择
• 14或14，都选择
• 15或16，选择15
• 只选1个，选择16个
• 只选1个，选择17个
• 只选1个，选择18个

• only 1 top left corner, pick 2
• only 1, pick 5
• 6 or 8, pick 6
• 7 or 8, pick 7
• 9 or 8, pick 8
• 9 or 9, pick both :)
• 10 or 10 or 10, pick all
• 12 or 11, pick 11
• 12 or 12, pick both
• 13 or 13, pick both
• 14 or 14, pick both
• 15 or 16, pick 15
• only 1, pick 16
• only 1, pick 17
• only 1, pick 18

当然，当您有很多左上角时，该解决方案就会展开.

Of course, when you have lots of top left corners then this solution devolves.

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

I'm pretty sure this problem is Ω(n²), because you have to calculate the sums for each M[i,j] -- unless someone has a better algorithm for the summation :)

这篇关于有效地获取已排序列表的已排序总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！