我会在底部解释问题的来源，但这是声明。假设我有两个非负整数列表，我将写成 (A[0] ... A[n]) 和 (B[0] ... B[米])。它们是严格递增的，因此 A[i+1] > A[i] 对于所有 i 并且对于 B 也是如此。我想按总和的升序收集所有 n * m 对元素。
因此，例如，如果 A = (0 1 2) 和 B = (1 4)，那么我想最终收集 ((0 1) (1 1) (2 1) (0 4) (1 4) (2 4))。如果有平局，我不关心我收集这两个元素的顺序。例如，如果 A = (0 1) 和 B = (0 1)，那么我不介意先选择 (0 1) 或 (1 0) 中的哪一个。
显然，我希望它能相当高效。我希望时间渐近到 m * n 是可能的。具体来说，如果我对输入一无所知，我希望有序输入使这个问题比等效问题更容易。当我第一次问这个问题时，我在想的是我们必须存储的状态量。我希望有可能有一个恒定的数量，但这也许是不现实的。 (我试过的东西都失败了!)
代码实际上是用 Lisp 编写的，但我认为问题陈述几乎与它无关。输入最自然地以单链表的形式出现，但无论如何我都必须提前反转它们，所以如果随机访问是相关的，我可以使它们成为数组。如果它是相关的，我希望这主要是在非常小的列表上调用，因此运行时的大量常数项/常数因子可能会排除解决方案。 (虽然我很想听听算法的想法!)
背景:我一直在研究计算机代数系统 Maxima 的源代码，尤其是它的两个多项式相乘代码。多项式以“稀疏格式”表示，因此 x^5 + x^2 + 2 可能显示为 (5 1 2 1 0 2)，后跟降序指数由各自的系数。为了有效地计算产品，我真正想做的是收集零次项，然后是 1 次项等。当前代码通过半心半意地提高效率来避免解决这个问题，然后做一个一种通用多项式加法，以按它不期望的顺序处理系数。我觉得我们应该可以做得更好!
最佳答案
这个问题与排序 X + Y 只是表面上的不同，后者是多年来计算几何学家的主要烦恼。 (请参阅 Joseph O’Rourke’s (open) Problem 41。)要为实现者总结该链接，可以添加和比较指数时最快的已知算法是 O(m n log (m n))，这是显而易见的算法。如果指数是有界整数，则适用彼得的傅立叶方法。很多聪明人已经思考这个问题很长时间了，所以我不希望很快出现更好的算法。
关于algorithm - 以递增顺序迭代数字对，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20459724/