LuanJunYi
BAN USER
Comments (4)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
I thought of a O(k*(logm + logn) solution.
The idea is to find the 1th minimum sum(which is a1+b1), the 2nd minimum sum, the 3rd..., until the kth minumum sum.
Denote the ith minimum sum is min(i). The key observation is that if min(i) = a(p) + b(q), min(i+1) is either a(p+1) + b(x) or a(y) + b(q+1), where b(x) is the minimum element in array b that hold b(x) + a(p+1) >= min(i), a(y) is the minimum element in array a that hold a(y) + b(q+1) >= min(i). min(i+1) is the smaller of the two.
Obviously, m(1) = a(1) + b(1), from where we can use iteration to compute m(k). Use binary search to locate a(x) need log(m) time, and locate b(y) need log(n) time. So k iteration need O(k*(logm + logn)) time.
Request for your comments.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Correct solution. Besides, I think the same algorithm can be extended easily for input with negative elements in it.
- LuanJunYi January 07, 2013