If we have a set S_k = {(i,j)} , such that every pair (x,y) whose
sum(x,y) < min{Sk} is already output,
then the next one to output is min{Sk} = sum(mi,mj), output it.
we can obtain S_(k+1) = Sk \ {(mi,mj)} U {(mi,mj+1),(mi+1,mj)},
also for every pair (x,y) whose sum(x,y)<min{S_(k+1)} is already
output...
Let S1 = {(1,1)}, repeat this procedure, until k elements are all
output.
Using a min-heap, this can be computed in O(klogk).
I think this is right.
Please correct me if I'm wrong.
Best regards.
On 11月30日, 上午4时22分, "Suranjit Adhikari"
<[EMAIL PROTECTED]> wrote:
> Problem
>
> Consider two sorted arrays of arbitary size, The aim is to find k minimum
> sums with the condition that there must be elements from both
> arrays in each sum. What is the best possible way to do this o(klogk) ?
>
> example input
> array1 = [1,2,3,4,5,6,7]
> array2= [3,4,7,9,15,17,25]
>
> find 3 smallest sums
>
> output : [4] =[3+1]
> [5]= [3+2]
> [5]=[4+1]
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
