在线性空间中存储成对求和

Question

如果我们有两个大小为n的数组，并且想要对它们的总和进行排序，那么朴素的方法是将它们的总和存储在O(n^2)的空间中，并在O(n^2 logn)的时间内进行排序。假设我们被允许具有相同的O(n^2 logn)运行时间，则如何将这些总和存储在O(n)线性空间中？

我认为我们并不打算存储所有总和，因为n^2个元素无法适应n的空间，而仅仅打印出所有按排序顺序排列的内容，这是否意味着我们必须动态存储项目？有什么提示吗？

（这是一个家庭作业问题）

- maregor

---

“两个数组之和”具体是什么意思？请提供一个带有预期输出的示例以及您迄今为止尝试过的内容。 - igon

如果我们有1 2 3 4 5和2 3 4 5 6，那么它们的总和将是3 4 5 6 7 4 5 6 7 8 5 6 7 8 9 6 7 8 9 10 7 8 9 10 11。 - maregor

Answer 1

我理解的问题是，我们想要找到总和。

a1 + b1  a1 + b2  ...  a1 + bn
a2 + b1  a2 + b2  ...  a2 + bn
  ...      ...    ...    ...
an + b1  an + b2  ...  an + bn

并按排序顺序打印它们。限制条件是在此过程中仅使用O（n）内存和O（n ^ 2 log n）时间。 将上表视为每个具有n个元素的n个列表（行）。如果我们对初始数组进行排序，使得a1 <= a2 <= ... <= an和b1 <= b2 <= ... <= bn，则每个列表已经排序。现在，问题被简化为合并n个排序列表。 为了设计这个算法，请考虑如何合并两个排序列表（如MergeSort），然后是三个列表，以此类推。这可以轻松地扩展到将每个长度为n的n个列表合并为一个输出元素需要n次操作，总共需要O（n ^ 3）次操作。现在，剩下的就是将获取每个输出元素的时间缩短到O（log n）的步骤。由于您只要求提示而不是完整的解决方案，请自己思考如何完成此步骤。

- Gassa

---

您提到您想要合并n个已排序的列表。如果这n个列表本身占用的空间超过n个空间，我们如何将所有这些列表合并到n个空间中？ - maregor

@maregor 列表并没有被明确地储存。相反，我们只是储存了一个指向遍历该列表停止位置的指针。例如，如果我们现在想要第9个列表中的第四个元素，我们知道它是 a9 + b4。如果我们选择消耗（输出）该元素，则该列表中的指针移动到其第五个值，即 a9 + b5。指针只是从 1 到 n+1 的数字，最后一个数字意味着该列表已经被耗尽。 - Gassa

那么这两个数组的排序时间就是 O(nlogn) + O(nlogn) 对吗？ - maregor

是的，因为它们都是大小为“n”的，我们独立地对它们进行排序。 - Gassa

一旦两个数组排序完成，我考虑在每个数组上放置一个指针来累加它们的总和并打印出来，但这可能不太可行，而且O(n)空间可能无法使用。我应该只将第一个列表存储在O(n)空间中，并将其他可能的列表与其进行比较吗？ - maregor

Answer 2

在Python中，您可以像这样做：

import heapq

a = [2, 1, 3]
b = [4, 6, 5]

a.sort()
b.sort()

def add_to_b(x):
    for v in b:
        yield v + x

for v in heapq.merge(*[add_to_b(x) for x in a]):
    print v

结果：

5
6
6
7
7
7
8
8
9

思路是我们对两个数组进行排序。然后将a的元素添加到b中，就定义了一个递增数的生成器。因此，我们创建n个这样的生成器，并使用heapq.merge将它们合并。在特定时间表示的生成器（由上面的add函数表示）需要常数空间（保持在b中的当前位置所需的空间）。heapq.merge本身需要线性空间。因此，算法的执行需要线性空间。

- JuniorCompressor

---

哇，这是一个非常简短的实现！Python 在这里真的很出色。 - Gassa

你能解释一下这段代码吗：for v in heapq.merge(*map(add, a))：？我不是很擅长Python，需要一些解释。 - maregor

[add_to_b(x) for x in a] 会为 a 中的每个 x 创建一个生成器。该生成器将 x 添加到 b 的每个元素中。我们将这些生成器序列传递给 heapq.merge 函数进行合并。 - JuniorCompressor

add_to_b函数将b中所有v元素相加，但你却将a中的所有元素传递给它。我该如何可视化这个过程？ - maregor

如果 a = [1, 2, 3]，b = [4, 5, 6]，那么 add_to_b(1) 将生成 1 + 4, 1 + 5, 1 + 6，add_to_b(2) 将生成 2 + 4, 2 + 5, 2 + 6，add_to_b(3) 将生成 3 + 4, 3 + 5, 3 + 6。因此，我们有三个序列 a) 5, 6, 7 b) 6, 7, 8 c) 7, 8, 9 需要合并。 - JuniorCompressor

Answer 3

首先按升序对这两个数组进行排序，时间复杂度为 2 * O(n*lgn)，也可以视为 O(n*lgn)。然后使用一个长度为 n + 1 的 最大堆 来维护最小的 n 个和。

如何维护最小的 n 个和？首先将 a1 + b1、a1 + b2、a1 + b3 等加入堆中。然后对于每个 a[i]，1 <= i < n 和 b[j]，0 <= j < n，将 a[i] + b[j] 加入堆中，然后弹出最大值：

for(int j=0;j<n;j++) {
    heap.push_into(a[0] + b[j]);
}
for(int i=1;i<n;i++) {
    for(int j=0;j<n;j++) {
        heap.push_into(a[i] + b[j]);
        heap.pop(); // remove the current largest sum in the heap, then the sums remain in the heap are the smallest n sums
    }
}

那么堆中的n个元素就是最小的n个和。

时间复杂度为O(n^2 * lgn)，空间复杂度为O(n)。

- coderz