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

需要提示设计了一个高效的算法，它采用以下输入并吐出以下输出。有效排序的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）空间复杂度算法。

必须有一个更好的算法，因为我没有利用排序输入数组的性质。

来源

2010-11-28 Srikanth

如果有这比O（ñ²日志ñ），它需要做的不仅仅是利用A和B已经被排序的事实，更好的解决方案。看到我的回答this question。

SRIKANTH想知道如何可以在O完成（ñ）空间（不包括用于输出的空间）。这可以通过懒惰地生成列表来完成。

假设我们有A = 6,7,8和B = 3,4,5。首先，通过在B中的第一个元素乘以所述的每个元素，并且这些存储在一个列表中：

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

发现该列表（6×3）的最小元素，它输出，与该元件中的A倍在乙取代它的下一个元素：

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

查找该列表（7×3），将其输出的新的最小元素，和替换：

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

依此类推。我们只需要该中间列表的O（）空间，并且如果我们将列表保留在heap中，则在每个阶段找到最小元素需要O（log n）时间。

来源

2010-11-28 22:35:09

感谢您提供链接。它肯定了这个问题不能比O（n^2logn）时间复杂度更好地解决的事实。它的有用技巧能够告诉（可能证明）给定问题的更紧密的下界。很明显，我们可以轻松地将我的问题缩减为您的链接所指向的问题，但我们可以在空间方面做些事情。可能是我可以通过少量或没有时间交易而不使用空间而逃脱。 – Srikanth 2010-11-28 22:53:32

如果您可以随时生成矩阵，而不是将其存储起来，那么您只使用O（* n *）空间（不计算输出空间）。 – 2010-11-28 22:56:35

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

来源

2010-11-29 11:03:38 Landei

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

回答

相关问题