Share my O(log(m+n)) code with some thought about it


  • 0
    H

    Like many other one's code, the main difficulty is to find the kth smallest element from two sorted arrays with time complexity O(log(m+n)). Why this is possible is that this algorithm jumps the ones which CANNOT be the kth smallest element.

    Here I give some examples showing how to understand this algorithm,

    1. We want to rule out the 1,2,...,k-1th smallest elements of both arrays.

    2. If k = 10, then k is larger than 9 elements, we can have that either array1[0] or array2[0] is one of those 9 elements. (Otherwise, array1[0] and array2[0] are larger than this kth elements which leads to a contradiction)

    3. Through (2), if we want to rule out the 1,2,...,k-1 smallest elements, we can have conclusion that, either array1[k/2-1] or array2[k/2-1] is one of those k-1 elements. WLOG, say it's array1[k/2-1], elements from 0 to k/2-1 of array1 can be ignore.

    4. From (3), we have shrink the problem size. We can use recursion to solve the smaller problem.

    The Java code is following,

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if((nums1.length + nums2.length) % 2 == 0){
            double d1 = getkth(nums1, 0, nums2, 0, (nums1.length + nums2.length)/2);
            double d2 = getkth(nums1, 0, nums2, 0, (nums1.length + nums2.length)/2+1);
            return (d1+d2)/2;
        }else{
            return getkth(nums1, 0, nums2, 0, (nums1.length + nums2.length)/2+1);
        }
    }
    private double getkth(int[] n, int ni, int[] m, int mi, int k){
        if(ni == n.length)
            return m[mi+k-1];
        if(mi == m.length)
            return n[ni+k-1];
        if(k == 1)
          return  (n[ni] < m[mi]) ? n[ni] : m[mi];
        
        int i = (k/2+ni > n.length) ? n.length : k/2+ni;
        int j = (k/2+mi > m.length) ? m.length : k/2+mi;
        if(n[i-1] < m[j-1])
            return getkth(n, i, m, mi, k-(i-ni));
        else
            return getkth(n, ni, m, j, k-(j-mi));
    }

Log in to reply
 

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