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


  • 2
    X

    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);
        
    }
    

    }


  • 0
    L

    @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.


  • 1
    G

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


  • 0
    X

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


  • 0
    S

    @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.


  • 0
    L

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


  • 0
    L

    @gofreesky Thank you.


  • 0
    L

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


Log in to reply
 

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