4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Array类题目

这个题目是找两个有序数组的中位数，首先跟数组元素个数的奇偶性有关。 若是奇数，则即为中间的数；若是偶数，则为中间两个数的平均值。

因此，解题思路为写一个辅助函数，找出两个数组中顺序为k的元素，则奇偶的情况都可解决。 因为题目要求时间复杂度为 O(log (m+n))，因此我们可以考虑二分查找的思想。 将两个数组a和b都划分为两部分，长度与k成正比，得到a和b在划分点的元素。 若a[aMid]>b[bMid]，则可删去a的后半部分和b的前半部分，目标元素的顺序k相应做调整，然后递归调用即可。

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        if((len1+len2) % 2 != 0) {
            // if odd
            return findKth(nums1, nums2, (len1+len2)/2, 0, len1-1, 0, len2-1);
        } else {
            // if even
            return (findKth(nums1, nums2, (len1+len2)/2-1, 0, len1-1, 0, len2-1) + findKth(nums1, nums2, (len1+len2)/2, 0, len1-1, 0, len2-1))/2;
        }
    }
    
    private double findKth(int[] a, int[] b, int k, int aStart, int aEnd, int bStart, int bEnd) {
        // k starts from 0
        int aLen = aEnd - aStart + 1;
        int bLen = bEnd - bStart + 1;
        if(aLen == 0) {
            return b[bStart + k];
        }
        if(bLen == 0) {
            return a[aStart + k];
        }
        if(k == 0) {
            return a[aStart] < b[bStart] ? a[aStart] : b[bStart];
        }
        // [aStart, aMid-1], [bStart, bMid-1] have k-1 elements 
        int aDiv = aLen * k / (aLen + bLen);
        int bDiv = k - aDiv - 1;
        int aMid = aStart + aDiv;
        int bMid = bStart + bDiv;
        if(a[aMid] == b[bMid]) {
            return a[aMid];
        }
        if(a[aMid] > b[bMid]) {
            // remove [bStart, bMid], [aMid+1, aEnd]
            k -= (bMid - bStart + 1);
            aEnd = aMid;
            bStart = bMid + 1;
        } else {
            // remove [aStart, aMid], [bMid+1, bEnd]
            k -= (aMid - aStart + 1);
            bEnd = bMid;
            aStart = aMid + 1;
        }
        return findKth(a, b, k, aStart, aEnd, bStart, bEnd);
    }
}