需要提示来设计一种有效的算法，该算法采用以下输入并吐出以下输出。
输入：两个排序的整数数组 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) 空间复杂度算法。
必须有更好的算法，因为我没有利用输入数组的排序特性。
如果有一个比 O(n²logn) 更好的解决方案，它需要做的不仅仅是利用 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 ) 时间。
如果将 A 的值与 B 的所有值相乘，结果列表仍然是排序的。在您的示例中：
A 是 1、3、5
B 是 4、8、10
1*(4,8,10) = 4,8,10
3*(4,8,10) = 12,24,30
现在您可以合并两个列表（就像在合并排序中一样）。您只需查看两个列表标题并将较小的标题放入结果列表中。所以在这里你会选择 4，然后是 8，然后是 10 等等。结果 = 4,8,10,12,24,30
现在您对结果列表和下一个剩余列表执行相同的操作，将 4,8,10,12,24,30 与 5*(4,8,10) = 20,40,50 合并。
由于如果两个列表具有相同的长度，合并是最有效的，您可以通过将 A 分成两部分来修改该模式，对两个部分进行递归合并，然后合并两个结果。
请注意，您可以使用合并方法节省一些时间，因为不需要对 A 进行排序，只需要对 B 进行排序。