题目

描述

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

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

则中位数是 2.0

示例 2:

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

则中位数是 (2 + 3)/2 = 2.5

解答

思路

既然是正序数组，只需要找到位于长度一半位置的元素就好了。

代码

class Solution {
 
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 如果一个数组为空，直接返回另外一个数组的中位数
        if (nums1.length == 0) {
            if (nums2.length % 2 == 0) {
                return (nums2[nums2.length / 2 - 1] + nums2[nums2.length / 2]) / 2.0D;
            } else {
                return (nums2[nums2.length / 2] + nums2[nums2.length / 2]) / 2.0D;
            }
        }
        if (nums2.length == 0) {
            if (nums1.length % 2 == 0) {
                return (nums1[nums1.length / 2 - 1] + nums1[nums1.length / 2]) / 2.0D;
            } else {
                return (nums1[nums1.length / 2] + nums1[nums1.length / 2]) / 2.0D;
            }
        }
        // 两个数组分别往后遍历，找到位于长度一般的位置的数字，就是中位数
        int i1 = -1, i2 = -1;
        for (int i = 0; i < (nums1.length + nums2.length + 1) / 2; i++) {
            if (nums1[i1 + 1] > nums2[i2 + 1]) {
                i2++;
            } else {
                i1++;
            }
        }
        if (i1 == -1) {
            return (nums2[i2] + nums2[i2 - 1]) / 2.0D;
        } else if (i2 == -1) {
            return (nums1[i1] + nums1[i1 - 1]) / 2.0D;
        } else {
            return (nums1[i1] + nums2[i2]) / 2.0D;
        }
    }
}