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,高效算法的时间复杂度不会超过O(n ^ 2)。

2)首先,我尝试了一种简单但效率低下的方法。生成A和B的笛卡尔积。可以在O(n ^ 2)时间复杂度下完成。我们需要存储,以便可以对其进行排序。因此,O(n

^ 2)空间复杂度也是如此。现在,我们对n ^ 2个元素进行排序,如果不对输入进行任何假设,则它们不能比O(n ^ 2logn)做得更好。

最后,我有O(n ^ 2logn)时间和O(n ^ 2)空间复杂度算法。

必须有一个更好的算法,因为我没有利用输入数组的 特性。

回答:

如果有这比O(解决 ñ ²登录 ñ),它需要做的不仅仅是利用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 ×3 = 24

在此列表中找到新的最小元素(7×3),将其输出并替换:

6×4 = 24、8×3 = 24、7

等等。我们只需要O( n

)空间用于此中间列表,并且如果将列表保留在堆中,则在每个阶段查找最小的元素将花费O(log

n )时间。

以上是 2个整数排序数组的有效排序笛卡尔积 的全部内容, 来源链接: utcz.com/qa/420194.html

回到顶部