efficient sorted Cartesian product of 2 sorted arr

问题:

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.

回答1:

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:

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

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

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

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

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:

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.