题目描述

给定两个大小为 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

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

解法1

解法1使用Binary Search。考虑两个排序数组nums1nums2,合并后后形成有序数组nums。记|nums1| = n1, |nums2| = n2, |nums| = n, 有n = n1 + n2。对nums求中位数,那么需要取nums的第k个数(n是奇数)或与第k+1个数取平均(n是偶数),其中k = (n + 1) / 2。

nums的这前k个数可能来自于nums1一部分和nums2一部分,我们用m1表示数字来自于nums1的个数,m2表示数字来自于nums2的个数,那么有 m1 + m2 = k。

现在的问题是如何确定m1?我们绘制一张图片来分析中位数的来源。A[i]表示数组nums1的元素;B[i]表示nums2的元素;C[i]表示nums的元素。

图1 中位数来源

前面说过,nums的前k个数分别来自于nums1的前m1个与nums2前m2个,那么C[k-1] = max{A[m1-1], B[m2-1]}, C[k] = min{A[m1], B[m2]}(这样nums1与nums2合并才能使得nums有序)。又因为C[k-1] <= C[k],所以max{A[m1-1], B[m2-1]} <= min{A[m1], B[m2]}。为了满足这个条件,就要求A[m1-1]<=B[m2]且B[m2-1] <= A[m1]。也就是说,我们寻找m1使得“A[m1-1]<=B[m2]且B[m2-1] <= A[m1]”成立就可以了。

为了寻找满足条件的m1,我们可以对数组nums1进行二分查找。如果A[m1-1] > B[m2]说明m1取的太大了;如果B[m2-1] > A[m1]说明m1取得太小了。

现在有一个边界问题需要考虑,如果m1 == 0,说明nums数组的前k个数不会来自于nums1,我们就取nums2[m2-1]作为C[k-1];如果m1 == |nums1|,说明我们要取nums1所有元素作为nums的前k个数,那么只能取nums2[m2]作为C[k]。同理,对于m2 == 0与m2 == |nums2|做相同的处理即可。

时间复杂度O(log(min(|nums1|, |nums2|)),空间复杂度O(1)。全部代码如下。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 我们总对短的数组进行binary search
        if (nums2.length < nums1.length)
            return findMedianSortedArrays(nums2, nums1);
        int n = nums1.length + nums2.length;
        int k = (n + 1) / 2;
        int l = 0, r = nums1.length;

        while (l <= r) {
            // 0<= m1 <= |nums1|
            int m1 = (l + r) >>> 1;
            int m2 = k - m1;

            if (m1 != 0 && m2 != nums2.length && nums1[m1 - 1] > nums2[m2])
                r = m1 - 1;
            else if (m2 != 0 && m1 != nums1.length && nums2[m2 - 1] > nums1[m1])
                l = m1 + 1;
            else {
                // 进入此分支说明m1,m2越界,或者正好找到了一个m1,m2使得A[m1-1]<=B[m2]且B[m2-1] <= A[m1]成立
                int leftMax, rightMin;

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

                if (m1 == nums1.length)
                    rightMin = nums2[m2];
                else if (m2 == nums2.length)
                    rightMin = nums1[m1];
                else {
                    rightMin = Math.min(nums1[m1], nums2[m2]);
                }
                return (leftMax + rightMin) / 2.0;
            }
        }

        return 0;
    }
}

参考:

  1. https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/
  2. https://zxi.mytechroad.com/blog/algorithms/binary-search/leetcode-4-median-of-two-sorted-arrays/
pwrliang Algorithms, Array, Binary Search

Leave a Reply

Your email address will not be published. Required fields are marked *