题目描述

给定两个大小为 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) {
         // 若仅当nums1为空
        if (nums1 == null || nums1.length == 0) {
            int length = nums2.length;
            int middle = length / 2;
            if (length % 2 == 0) {
                return (nums2[middle] + nums2[middle - 1]) / 2.0;
            } else {
                return nums2[middle];
            }
        }
        // 若仅当nums2为空
        if (nums2 == null || nums2.length == 0) {
            int length = nums1.length;
            int middle = length / 2;
            if (length % 2 == 0) {
                return (nums1[middle] + nums1[middle - 1]) / 2.0;
            } else {
                return nums1[middle];
            }
        }
        int len1 = nums1.length;
        int len2 = nums2.length;
        int middle = (len1+len2)/2;
        int currentIndex = 0;

        int i1 = 0, i2 = 0;
        int last = 0, current = 0;

        while(currentIndex <= middle){
            currentIndex++;
            last = current;

            /**
             * 注意越界情况：
             * 比如，
             * 1 2 3 4
             * 5 6 7 7 8 9
             * 当然，数组为空的情况也包含在这里面
             */
            // i1越界
            if(i1 == len1){
                current = nums2[i2];
                i2++;
                continue;
            }
            // i2越界
            if(i2 == len2){
                current = nums1[i1];
                i1++;
                continue;
            }

            // 正常操作
            if(nums1[i1] <= nums2[i2]){
                current = nums1[i1];
                i1++;
            } else {
                current = nums2[i2];
                i2++;
            }
        }

        // 分奇偶情况
        if((len1+len2) % 2 == 0){
            return (last + current) / 2.0;
        } else {
            return current;
        }

    }
}

题目描述

题解代码

提交

更多题解