# Share my java solution O(log(min(m,n)))

• If we want to find the top K element, we can first of all get rid of the top K-1 elements.
Take K/2 elements from nums1 and nums2. Because they are all sorted. So

if nums1[k/2-1] < nums2[k/2-1]
or nums2 has not enough K/2 elements
then nums1 = nums[k/2,end] (delete nums1[0,k/2-1])

we can guarantee nums1[0,k/2-1] is smaller than the top Kth element.
Now we only need to find the top K-K/2 element in the rest of nums1(deleted k/2 elements) and nums2
If K == 1, that means we need find the min value of nums1 and nums2.

``````public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int leftMedian = (nums1.length+nums2.length+1)/2;
int rightMedian = (nums1.length+nums2.length+2)/2;
return (helper(nums1,0,nums2,0,leftMedian)+helper(nums1,0,nums2,0,rightMedian))/2.0;
}

public double helper(int[] nums1, int start1, int[]nums2, int start2, int topK){
if(start1 > nums1.length-1) return nums2[start2+topK-1];
if(start2 > nums2.length-1) return nums1[start1+topK-1];
if(topK == 1) return Math.min(nums1[start1],nums2[start2]);

if(start2+topK/2-1 > nums2.length-1) return helper(nums1,start1+topK/2,nums2,start2,topK-topK/2);
if(start1+topK/2-1 > nums1.length-1) return helper(nums1,start1,nums2,start2+topK/2,topK-topK/2);

if(nums1[start1+topK/2-1] < nums2[start2+topK/2-1]) return helper(nums1,start1+topK/2,nums2,start2,topK-topK/2);
else return helper(nums1,start1,nums2,start2+topK/2,topK-topK/2);

}
``````

}

• @xuechao Your solution seems to be wrong when I tried the following input.

nums1: [416, 850]
nums2: [899, 540]

The expected median should be (540+850)/2=695 because of this: [416, 540, 850, 899]. But your code returns 874.5.

Thanks.

Thanks.

• @Longstation you need to make sure the array sorted,so the input of [899, 540], you need [540, 899]

• @Longstation please see @gofreesky 's post. As he said,the input should be sorted first. Hope this helps!

• @xuechao O(log(m + n)) rather than min(m, n) is it not? k start with (m + n)/2 and cut by half on each iteration.

• I have tried your code, but " Time Limit Exceeded" showed.

• @gofreesky Thank you.

• @xuechao Yes. Both of you are right. Thanks.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.