Since the arrays are sorted, you should be able to do this in O(n) time.
a[1..n], b[1..n]
output a[n], b[n]
int count=1;
while (i > 0 and j > 0 and count < n)
Begin
if (a[i-1] * b[j] >= a[i] * b[j-1])
Begin
Output a[i-1] & b[j]
i=i-1;
End
else
Begin
Output a[i] & b[j-1]
j = j-1;
End
++count;
End
On Mon, Aug 9, 2010 at 6:36 PM, amit <[email protected]> wrote:
> Given two sorted positive integer arrays A(n) and B(n), we define a
> set S = {(a,b) | a \in A and b
> \in B}. Obviously there are n2 elements in S. The value of such a pair
> is defined as Val(a,b) = a +
> b. Now we want to get the n pairs from S with largest values.
>
> How to do this in O(nlogn) time.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
