有效排序的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²日志 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），输出它，将其替换为B：B：B：

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

找到此列表的新元素（7×3），输出并替换：

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

等等。我们只需要o（n）此中间列表的空间，并在每个阶段找到最小的元素为O（日志） n）如果我们将清单保存在一个 堆.

Answer 2

如果将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进行排序。