Share my simple and straightforward O(log(m+n)) solution with explanation, Java


  • 0
    G

    public class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length + nums2.length;
        if(n%2 == 1){ return (double) findTheKthElement(nums1, nums2, 0, nums1.length - 1, 0, nums2.length - 1, n/2 + 1);}
        int ele1 = findTheKthElement(nums1, nums2, 0, nums1.length - 1, 0, nums2.length - 1, n/2);
        int ele2 = findTheKthElement(nums1, nums2, 0, nums1.length - 1, 0, nums2.length - 1, n/2 + 1);
        return (ele1 + ele2)/2.0;
    }
    

    The following function finds the kth elements given only nums1[low1, ..., high1] and nums2[low2, ..., high2].
    It works this way: suppose we have two subarray of nums1 and nums2.

    nums1[low1, ..., mid, ..., high1]

    nums2[low2, ..., j, ..., high2]

    we first find the position nums1[mid] should be in nums2 if we want to insert it, we can use binary search to do that. Let's say we find that it should be j in nums2. Now we can know the rank of nums1[mid]. if the rank is equal to k, done, we return it. if the rank is smaller than k, we can discard all the elements from low1 to mid of nums1, and low2 to j of nums2. we search the (k-rank)th element in what is left, i.e., nums1[mid+1, ..., high1] and nums2[j, ..., high2]. This time we use the mid point of nums2[j, ..., high2] and find the insert position should be in nums1[mid+1, high1];

    We recursively do this until we find it.

    public int findTheKthElement(int[] nums1, int[] nums2, int low1, int high1, int low2, int high2, int k){
        if(low1 > high1){
            return nums2[low2+k-1];
        }
        int mid = low1 + (high1 - low1)/2;
        int index = biSearch(nums2, nums1[mid], low2, high2);// the position nums1[mid] should be in nums2.
        int rank = (mid - low1 + 1) + (index - low2); // the rank of nums1[mid].
        if(rank == k){ return nums1[mid];}
        else if(rank < k){
            if(index == high2 + 1){
                return nums1[mid + (k-rank)];
            }
            return findTheKthElement(nums2, nums1, index, high2, mid+1, high1, k - rank);
        }
        else{
            if(index == high2 + 1){
                return findTheKthElement(nums2, nums1, low2, high2, low1, mid-1, k);
            }
            return findTheKthElement(nums2, nums1, low2, index, low1, mid-1, k);
        }
    }
    

    // The following function return the index that the target should be in subarray nums[low, ..., high].

    // Suppose nums[low, ..., high] is [1,5,6], and low == 0, high == 2;

    // if target == 0, it returns 0; if target == 2, it returns 1; if target == 8, it returns 3;

    public static int biSearch(int[] nums, int target, int low, int high){
        if(low > high){ return low;}
        if(nums[high] <= target){ return high + 1;}
        while(low < high){
            int mid = low + (high - low)/2;
            if(nums[mid] == target){ return mid;}
            if(nums[mid] > target){
                high = mid;
            }
            else{
                low = mid + 1;
            }
        }
        return high;
    }
    

    }


  • 0
    B

    Is there any reason that you take turns to access the two arrays ie, first finding the position of nums1's mid in the nums2, then the position of nums2's in nums1?


Log in to reply
 

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