LeetCode百题【寻找两个正序数组的中位数】

题目描述

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

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

1
2
3

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

1
2
3

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

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

解法

二分查找
- 整体思路：
- 用一条分割线，将两个数组从中间一分为二分成四个部分
  - 1.left 1.right
  - 2.left 2.right
- 中位数就是max(left)+min(right)的和除以2
- 此题的关键就是如何寻找分割线的位置
具体细节在代码中

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //eg：
        //m：1 2 3
        //n：4 5 6 7 8 9
        //1.保证nums1是长度最短的数组，方便统一一计算
        if (nums1.length > nums2.length) {
            int[] tmp = nums2;
            nums2 = nums1;
            nums1 = tmp;
        }
        int m = nums1.length;
        int n = nums2.length;

        //2.合并后分割线左边的元素的个数满足(m+n+1)/2
        //规定奇数下中位数分到左边的数组
        //偶数不会因为+1而影响
        int totalLeft = (m + n + 1) / 2;

        //3.准备二分查找(根据m数组找分割线)
        int left = 0;
        int right = m;
        while (left < right) {
            int i = left + (right - left + 1) / 2;
            //定义i：nums1[i]为nums1右数组的最小值，也就是在分割线右边的值
            //同理 nums1[i-1]为nums1左数组的最大值，也就是在分割线左边的值
            //这里取中间值原本应该为left+middle->(right-left)/2;
            //如果不+1会导致死循环,因为right-left最小为1，1/2->0 会导致i一直为left
            int j = totalLeft - i;
            //定义同上，剩下的就是nums2的
            if (nums1[i - 1] > nums2[j]) {
                //1左>2右，针对nums1来讲，取大了，二分区间需要向左缩
                right = i - 1;
                //->[left,i-1]
            } else {
                //相反
                //[i,right]
                left = i;//响应上边如果不+1而导致的的死循环
            }
        }
        //4.跳出循环，后 此时的分割线位置已经找到
        int i = left;
        int j = totalLeft - i;
        //nums1[i-1]&&nums1[i]
        //nums2[j-1]&&nums2[j]

        //5.考虑特殊情况
        //当nums1的分割线左边没有数时,防止下标越界，并且在去左边的最大值时保证它必定取不到
        //三元表达式 nums1leftmax=(i==0吗？)--->(yes->a,no->b)
        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        //当nums1的分割线右边没有数时,类比同上
        int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];

        //nums2同理
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];

        //6.考虑奇偶
        if ((m + n) % 2 == 1) {
            return Math.max(nums1LeftMax, nums2LeftMax);
        } else {
            return (double) (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2;
        }
    }
}