Keep priority queue of pairs - sum and respective indices in the
arrays.
Start from pair (a[0] + b[0], (0, 0)).
while (queue is not empty && n > 0) {
retrieve largest sum from the queue, (sum, (i, j))
add sum to the result array
--n;
add pairs (a[i + 1] + b[j], (i + 1, j)) and (a[i] + b[j + 1], (i, j
+ 1)) if it is possible due the boundings;
}
The additional care should be taken to avoid processing pair of
indices twice.
On 14 окт, 11:55, Harshal <[email protected]> wrote:
> Given two sorted postive integer arrays A[n] and B[n] (W.L.O.G, let's
> say they are decreasingly sorted), we define a set S = {(a,b) | a \in A
> and b \in B}. Obviously there are n^2 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. The tricky part is that we need an O(n)
> algorithm.
>
> --
> Harshal Choudhary,
> III Year B.Tech Undergraduate,
> Computer Engineering Department,
> National Institute of Technology Surathkal, Karnataka
> India.
--
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.
