4.寻找两个正序数组的中位数(困难)|Java刷题打卡-一一网

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

题目描述

来源：力扣（LeetCode）

链接：leetcode-cn.com/problems/me…

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]

输出：2.00000

解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]

输出：2.50000

解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例 3：

输入：nums1 = [0,0], nums2 = [0,0]

输出：0.00000

示例 4：

输入：nums1 = [], nums2 = [1]

输出：1.00000

示例 5：

输入：nums1 = [2], nums2 = []

输出：2.00000

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

进阶: 你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

题目分析

一般做法

如果我们不管进阶的要求，直接将两个数组合并成一个新的数组，然后将新数组排序，然后分别取得 (m+n)/ 2 和 ((m+n) - 1) / 2 两个位置的数，取两者平均值。这样取平均数是不用管合成的新数组的大小是奇数还是偶数的。

合并两个数组的复杂度是 O(m+n)，对合并数组进行排序的复杂度是 O((m+n)log(m+n))，整体的复杂度是 O((m+n)log(m+n))

二分搜索

既然要求时间复杂度为O(log(m+n))，而且数组是正序，那么自然而然就会想到用二分搜索。因为中位数左右两边元素个数是一样的，m = nums1.length,n= nums2.length,k=m+n,那么中位数左右两边元素个数都是k/2，如果 nusm1在中位数的左边有i个元素，那么nums2在中位数的左边就有j = k/2-i个元素。

i和j将两个数组分成了左右两部分，这时要满足的条件

nums1的左部的最大值要小于nums2右部的最小值
nums2左部的最大值小于nums1右部的最小值

要满足这个条件我们只需要改变i的大小就可以了，比如增大i，那么j就会减小，nums1在左边的最大值就会增大，nums2在右边的最小值就会减小

具体的做法可以看代码及注释

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        // 这个地方要保证nums1的长度不能比nums2大,否则j可能会小于0
        if (m > n) {
            return findMedianSortedArrays(nums2, nums1);
        }
        // 要使用二分查找，就是每次要去掉一半的数据，因为我们是要改变i的值，那么i的值就在[0,m]这个区间，
        // 第一次 i = m / 2 ,如果i的值大了，那么第二次查找区间就变成[0,m1]，这个m1就等于第一次的i,依次类推
        int iMin = 0;
        int iMax = m;
        while (true) {
            int i = (iMin + iMax) / 2;
            int j = (m + n + 1) / 2 - i;
            // 如果i大了，就向左找
            if (i > iMin && nums1[i - 1] > nums2[j]) {
                iMax = i - 1;
            } else if (i < iMax && nums2[j - 1] > nums1[i]) {//i小了就向右找
                iMin = i + 1;
            } else {
                // 这个边界判断其实还比较麻烦
                // 如果一共有奇数个元素，那么中位数就是左侧最大的那个
                // 左侧最大的那个就是Math.max(nums1[i - 1], nums2[j - 1])
                // 显然这里i和j为0的时候就不能用这个公式了

                int leftMax = 0;
                int rightMin = 0;

                if (i == 0) {
                    leftMax = nums2[j - 1];
                } else if (j == 0) {
                    leftMax = nums1[i - 1];
                } else {
                    leftMax = Math.max(nums1[i - 1], nums2[j - 1]);
                }
                if ((m + n) % 2 == 1) {
                    return leftMax;
                }

                // 如果一共有偶数个元素
                // 正常情况下rightMin = Math.min(nums1[i], nums2[j])
                // median = (leftMax + rightMin) / 2.0
                // i=m,j=n时，rightMin是不对的，所以又要处理边界
                if (i == m) {
                    rightMin = nums2[j];
                }else if(j == n) {
                    rightMin = nums1[i];
                }else {
                    rightMin = Math.min(nums1[i], nums2[j]);
                }
                if ((m + n) % 2 == 0) {
                    return (leftMax + rightMin) / 2.0;
                }
            }
        }
    }
}
复制代码