2排序整数数组的有效排序笛卡尔乘积
需要提示来设计一个高效的算法，该算法采用以下输入并吐出以下输出。
输入：两个整数数组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，Efficient算法无法比O（n ^ 2）的时间复杂度更好。
2）首先我尝试了一种简单但低效的方法。 生成A和B的Cartesian乘积。它可以在O（n ^ 2）时间复杂度下完成。 我们需要存储，所以我们可以对它进行排序。 因此O（n ^ 2）空间复杂度也是如此。 现在我们对n ^ 2个元素进行排序，而不是对输入进行任何假设，这比O（n ^ 2logn）要好得多。
最后我有O（n ^ 2logn）时间和O（n ^ 2）空间复杂度算法。
必须有更好的算法，因为我没有使用输入数组的排序性质。
如果存在一个比O（n 2 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中的下一个元素A代替它：
7×3 = 21,6 ×4 = 24,8 ×3 = 24
找到该列表中新的最小元素（7×3），输出它，并替换：
6×4 = 24,8×3 = 24,7 ×4 = 28
等等。 我们只需要这个中间列表的O（n）空间，并且如果我们将列表保存在一个堆中，在每个阶段找到最小的元素需要O（log n）时间。
如果将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进行排序。
链接地址: http://www.djcxy.com/p/3885.html上一篇: efficient sorted Cartesian product of 2 sorted array of integers