2排序整数数组的高效分选笛卡尔乘积 [英] efficient sorted Cartesian product of 2 sorted array of integers

问题描述

需要的提示以设计一个高效的算法，需要以下输入和吐出来的是下面的输出。

Need Hints to design an efficient algorithm that takes the following input and spits out the following output.

输入：整数A和B，每个长度为n

Input: two sorted arrays of integers A and B, each of length n

输出：一个排序的数组包含数组A和B的笛卡尔积

Output: One sorted array that consists of Cartesian product of arrays A and 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

下面是我在尝试解决这个问题。

Here are my attempts at solving this problem.

1）由于输出为n ^ 2，高效的算法，不能做任何比为O（n ^ 2）的时间复杂度。

1) Given that output is n^2, Efficient algorithm can't do any better than O(n^2) time complexity.

2）首先我想简单，但效率不高的方法。生成A和B的笛卡尔乘积它可以为O（n ^ 2）的时间复杂度来完成。我们需要存储，所以我们可以做就可以了排序。因此为O（n ^ 2）空间复杂了。现在，我们的排序N ^ 2元不能不做任何假设输入比为O（n ^ 2logn）做的更好。

2) First I tried a simple but inefficient approach. Generate Cartesian product of A and B. It can be done in O(n^2) time complexity. we need to store, so we can do sorting on it. Therefore O(n^2) space complexity too. Now we sort n^2 elements which can't be done better than O(n^2logn) without making any assumptions on the input.

最后，我为O（n ^ 2logn）时间为O（n ^ 2）空间复杂度的算法。

Finally I have O(n^2logn) time and O(n^2) space complexity algorithm.

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

There must be a better algorithm because I've not made use of sorted nature of input arrays.

推荐答案

如果有一个解决方案，它为O更好的（ N 的²登录的 N 的），它需要做的更多不仅仅是利用的事实，A和B已经排序。见我的回答这个问题。

If there's a solution that's better than O(n² log n) it needs to do more than just exploit the fact that A and B are already sorted. See my answer to this question.

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

Srikanth wonders how this can be done in O(n) space (not counting the space for the output). This can be done by generating the lists lazily.

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

Suppose we have A = 6,7,8 and B = 3,4,5. First, multiply every element in A by the first element in B, and store these in a list:

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

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

查找这个名单（6×3），其输出的最小元素，它与一个时代的下一个元素的元素B中替换：

Find the smallest element of this list (6×3), output it, replace it with that element in A times the next element in B:

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

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

查找这个名单（7×3），其输出的新的最小元素，并替换：

Find the new smallest element of this list (7×3), output it, and replace:

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

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

等。我们只需要O（ N 的）空间，这中间的列表，并找到最小的元素在每个阶段需要O（日志的 N 的）时间，如果我们保持在一个列表< A HREF =htt​​p://en.wikipedia.org/wiki/Heap_%28data_structure%29相对=nofollow>堆。

And so on. We only need O(n) space for this intermediate list, and finding the smallest element at each stage takes O(log n) time if we keep the list in a heap.

这篇关于2排序整数数组的高效分选笛卡尔乘积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！