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

Question

需要提示设计一个有效的算法,该算法采用以下输入并吐出以下输出.

输入:两个整数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)空间复杂度算法.

必须有一个更好的算法,因为我没有使用输入数组的排序性质.

Answer 1

如果有一个比 O( n \xc2\xb2 log n )更好的解决方案，那么它需要做的不仅仅是利用 A 和 B 已经排序的事实。请参阅我对这个问题的回答。

\n\n\n\n

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

\n\n

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

\n\n

\n

6\xc3\x973 = 18, 7\xc3\x973 = 21, 8\xc3\x973 = 24

\n

\n\n

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

\n\n

\n

7\xc3\x973 = 21, 6\xc3\x974 = 24 , 8\xc3\x973 = 24

\n

\n\n

找到该列表中新的最小元素 (7\xc3\x973)，输出它并替换：

\n\n

\n

6\xc3\x974 = 24, 8\xc3\x973 = 24, 7\xc3\x974 = 28

\n

\n\n

等等。我们只需要 O( n ) 空间来存储这个中间列表，如果我们将列表保存在堆中，则在每个阶段找到最小元素需要 O(log n ) 时间。

\n