题目:

4. 寻找两个有序数组的中位数

解法:

解法一:
最简单的办法就是合并两个有序数组, 因为数组有序, 所以很容易合并起来, 时间复杂度O(m+n);
然后取中位数即可.

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int len1 = nums1 != null ? nums1.length : 0;
    int len2 = nums2 != null ? nums2.length : 0;
    // 假设合并后的数组的长度
    int len = len1 + len2;
    int[] arr = new int[len];
    int index = 0;
    int i1 = 0;
    int i2 = 0;
    while (i1 < len1 && i2 < len2) {
        arr[index++] = nums1[i1] < nums2[i2] ? nums1[i1++] : nums2[i2++];
    }
    while (i1 < len1) {
        arr[index++] = nums1[i1++];
    }
    while (i2 < len2) {
        arr[index++] = nums2[i2++];
    }

    // 合并后的数组求 中位数
    double midNum = 0.0;
    if (len % 2 == 0) {
        // 偶数
        int mid = len / 2 - 1;
        midNum = (arr[mid] + arr[mid + 1]) / 2.0;
    } else {
        // 奇数
        int mid = len / 2;
        midNum = (double) (arr[mid]);
    }
    return midNum;
}

但是, 并不符合题目要求的时间复杂度 O(log(m + n)).
解法二:
见官方解答