4. Median of Two Sorted Arrays

LeetCode Link

Solution1 转化为 find Kth Smallest element.

将 kth 定义为 element 的个数比较好些代码和逻辑。

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int sumLen = nums1.length + nums2.length;
    if (sumLen % 2 != 0) {
        return (double)findKthSmallest(nums1, nums2, sumLen / 2 + 1, 0, 0);
    }
    
    int firstMedian = findKthSmallest(nums1, nums2, sumLen / 2, 0, 0);
    int secondMedian = findKthSmallest(nums1, nums2, sumLen / 2 + 1, 0, 0);
    
    return (firstMedian + secondMedian) / 2.0;
}

// starting with 1st
private int findKthSmallest(int[] nums1, int[] nums2, int kth, int start1, int start2) {
    if (start1 >= nums1.length) {
        return nums2[start2 + kth - 1];
    }
    if (start2 >= nums2.length) {
        return nums1[start1 + kth - 1];
    }
    if (kth == 1) {
        return Math.min(nums1[start1], nums2[start2]);
    }
    
    int step1 = Math.min(kth / 2, nums1.length - start1);       // check the boundary
    int step2 = Math.min(kth - step1, nums2.length - start2);   // check the boundary
    int index1 = start1 + step1 - 1;
    int index2 = start2 + step2 - 1;

    // if (nums1[index1] == nums2[index2] && step1 + step2 == kth) {
    //     // due to the boudary check, step1 + step2 <= kth
    //     // 也可以判断，哪一个可能越界，因为只可能有一个越界，另一个就是 kth - stepx；
    //     // 这样就可以一直保证 step1 + step2 == kth, 也可以保证真正的 O(log(m + n))
    //     return nums1[index1];
    // }
    
    if (nums1[index1] < nums2[index2]) {
        // nextKth: kth - step1
        return findKthSmallest(nums1, nums2, kth - step1, index1 + 1, start2);
    } else {
        // nextKth: kth - step2
        return findKthSmallest(nums1, nums2, kth - step2, start1, index2 + 1);
    }
}

Runtime: O(log(m + n))

Solution 2

iterate the small array with Binary Search, comparing to kth - mid in the bigger array.

runtime: O(min(m, n))

题解：http://zxi.mytechroad.com/blog/algorithms/binary-search/leetcode-4-median-of-two-sorted-arrays/