Qi Lu
BAN USER
Comments (4)
Reputation 5
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.
-1
of 1 vote
We suppose that the array after merging two sorted array is C.
We can solve this problem with time complexity O(log(lengthA + lengthB)).
This problem can be converted to the problem of finding kth element, k is (A’s length + B’ Length)/2. If we can solve the problem of finding kth element, we can solve this problem.
Fist suppose the number of A and B'elements are greater than K/2. We compare the A[k/2-1] and B[k/2-1]. If A[k/2-1] < B[k/2-1], this show that the elements from A[0] to A[k/2-1] are in the C's first K elements. So we can discard the elements from A[0] to A[k/2-1]. Then use recursion we can solve this problem.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
@kr.neerav If the cost of the shortest path from start node to end node is bigger than “magic potions”, there is no way to go to the end node.
- Qi Lu September 19, 2014