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）空间复杂性算法。
There must be a better algorithm because I've not made use of sorted nature of input arrays.
Need Hints to design an efficient algorithm that takes the following input and spits out the following output.
Input: two sorted arrays of integers A and B, each of length n
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) Given that output is n^2, Efficient algorithm can't do any better than O(n^2) time complexity.
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.
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果有一个比 O(n² log n) 更好的解决方案，它需要做的不仅仅是利用 A 和 B 已经排序的事实。请参阅我对此问题的回答。
Srikanth 想知道如何在 O(n) 空间（不计算输出空间）中完成此操作。这可以通过延迟生成列表来完成。
假设 A = 6,7,8，B = 3,4,5。首先，将 A 中的每个元素乘以 B 中的第一个元素，并将它们存储在列表中：
找到此列表 (6×3) 中的最小元素，输出它，用 A 中的该元素乘以 B 中的下一个元素替换：
找到该列表 (7×3) 中新的最小元素，输出并替换：
等等。我们只需要 O(n) 空间来存储这个中间列表，如果我们将列表保存在 < 中，则在每个阶段找到最小元素需要 O(log n) 时间。 a href="http://en.wikipedia.org/wiki/Heap_(data_struct)" rel="nofollow noreferrer">堆。
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 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.
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:
Find the smallest element of this list (6×3), output it, replace it with that element in A times the next element in B:
Find the new smallest element of this list (7×3), output it, and replace:
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.
如果将 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，依此类推。
result = 4,8,10,12,24,30
现在，您对结果列表和下一个剩余列表执行相同的操作，将 4,8,10,12,24,30 与 5*(4,8,10) = 20 合并,40,50。
由于如果两个列表具有相同的长度，合并效率最高，因此您可以通过将 A 分为两部分来修改该架构，对两个部分进行递归合并，然后合并两个结果。
请注意，使用合并方法可以节省一些时间，因为不需要对 A 进行排序，只需对 B 进行排序。
If you multiply a value of A with all values of B, the result list is still sorted. In your example:
A is 1, 3, 5
B is 4, 8, 10
1*(4,8,10) = 4,8,10
3*(4,8,10) = 12,24,30
Now you can merge the two lists (exactly like in merge sort). You just look at both list heads and put the smaller one in the result list. so here you would select 4, then 8 then 10 etc.
result = 4,8,10,12,24,30
Now you do the same for result list and the next remaining list merging 4,8,10,12,24,30 with 5*(4,8,10) = 20,40,50.
As merging is most efficient if both lists have the same length, you can modify that schema by dividing A in two parts, do the merging recursively for both parts, and merge both results.
Note that you can save some time using a merge approach as is isn't required that A is sorted, just B needs to be sorted.