2 个排序整数数组的高效排序笛卡尔积

Need Hints设计一个有效的算法，接受以下输入并输出以下输出。

输入：两个已排序的整数数组 A 和 B，每个数组的长度为 n

输出：一个排序数组，由数组 A 和 B 的笛卡尔积组成。

For Example: 

Input:
A is 1, 3, 5
B is 4, 8, 10
here n is 3.

Output:
4, 8, 10, 12, 20, 24, 30, 40, 50

这是我解决这个问题的尝试。

1）假设输出为n^2，高效算法不能比O(n^2)时间复杂度更好。

2）首先我尝试了一种简单但效率低下的方法。生成 A 和 B 的笛卡尔积。可以在 O(n^2) 时间复杂度内完成。我们需要存储，所以我们可以对其进行排序。因此空间复杂度也是O(n^2)。现在我们对 n^2 个元素进行排序，在不对输入进行任何假设的情况下，这不可能比 O(n^2logn) 更好。

最后我有 O(n^2logn) 时间和 O(n^2) 空间复杂度算法。

一定有更好的算法，因为我没有使用过sorted输入数组的性质。

如果有一个比 O(n² log n）它需要做的不仅仅是利用 A 和 B 已经排序的事实。请参阅我的回答这个问题.

Srikanth 想知道如何在 O(n) 空间（不计算输出空间）。这可以通过延迟生成列表来完成。

假设 A = 6,7,8，B = 3,4,5。首先，将 A 中的每个元素乘以 B 中的第一个元素，并将它们存储在列表中：

6×3 = 18, 7×3 = 21, 8×3 = 24

找到这个列表中的最小元素 (6×3)，输出它，用 A 中的该元素乘以 B 中的下一个元素替换：

7×3 = 21，6×4 = 24, 8×3 = 24

找到这个列表中新的最小元素（7×3），输出它，并替换：

6×4 = 24, 8×3 = 24,7×4 = 28

等等。我们只需要 O(n) 这个中间列表的空间，并且在每个阶段找到最小元素需要 O(logn）如果我们将列表保存在heap.