Hi, Quintopia,
Maybe you misunderstood my algorithm above.
S_k is a set of ordered pair (i,j)
each time we pop the min(S_k) from S_k, we insert at most 2 element in
it
so its size is in O(k)
I think the following should be more clear:
heap: MIN_HEAP
visited[n][n] =
Hi, ljb,
Let me have a try to prove the correctness of it.
Let define a property A(S) :
S is a set of ordered pair (i,j), and every
pair (x,y) whose sum(x,y) is less than min{S} = sum(mi,mj) is already
output.
Initially, we have S_1 = {(1,1)}, A(S_1) holds.
Suppose that for n, A(S_n) holds,
you're right. I didn't understand it. your solution is correct. My
version would only work in cases in which we didn't need to print the
same minimum sum as many times as it appears. . .but it wouldn't even
be very good at this.
In other words, I solved a completely different problem, yes?
If we have a set of S_k = {(i,j)} , such that every pair (x,y) whose
sum(x,y) max{Sk} is already output,
then the next one to output is min{Sk} = sum(mi,mj), then output it,
then 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)}
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
may be right, but how about this:
On input sorted arrays L and R
output[0] = L[0]+R[0]
i=0
j=0
p=0
for n=1 to k-1
if i+1size[L]
if j+1size[R]
error can't get k sums
else
j=j+1
else if j+1size[R]
i=i+1
else if
else if L[i+1]+R[j]R[j+1]+L[i]
j = j+1
I think O(klogk) is possible.
array1=A={a1,a2,...,},B=arrary2={b1,b2,..}
think about the 2-d grid generated by A,B ( all points (ai,bj)).
using a swap line x+y=c, swap these point until we have scaned k point.
maintain a heap to tell which point will be the next point we will
scan.
Moreover, if
The problem is infact finding the lowest numbers of the combined
arrays. For that you can use concept of merge algorithm of the merge
sort. That will work out in only O(nlogn) time.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to
