LeetCode 004 Median of Two Sorted Arrays 详细分析

LeetCode

题目链接：https://leetcode.com/problems/median-of-two-sorted-arrays/

我一直会卡在这道题上，在网上看了半个小时的博客，愣是没看懂。后来看到 YouTube 上有一个印度大哥的讲解，豁然开朗。

印度大哥的视频地址：Binary Search : Median of two sorted arrays of different sizes.

题目描述

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

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

The median is 2.0
Example 2:

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

The median is (2 + 3)/2 = 2.5

题目分析

其实这道题我卡就卡在，一直没有想清楚应该如何划分两个数组。直接看LeetCode论坛上的答案，也一直没有搞懂。本题只是想求中位数，并不用管其他的数字。

那么核心就在于，如何划分两个数组，使得两个数组组合起来后，成为一个在中位数附近相对有序的数组即可。

具体实例分析

算法分析

定义两个变量 partitionX、 partitionY，分别分割X数组和Y数组，记为X1, X2, Y1, Y2。使得

len(X1) + len(Y1) == len(X2) + len(Y2)
或
len(X1) + len(Y1) == len(X2) + len(Y2) + 1

并且使得 max(X1) < min(Y2), max(Y1) < min(X2)，这样数组就被完整地分成了两部分。

如果两个数组长度的和是奇数，那么必然是 max(X1, Y1)了；
如果两个数组长度的和是偶数，那么是 (max(X1, Y1) + min(X2, Y2)) / 2。

代码实现

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }
    int x = nums1.length, y = nums2.length;
    int low = 0, high = x;
    while (low <= high) {
        int partitionX = (low + high) / 2;
        int partitionY = (x + y + 1) / 2 - partitionX;
        int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
        int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
        int minRightX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
        int minRightY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];
        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            if ((x + y) % 2 == 0) {
                return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2.0;
            } else {
                return Math.max(maxLeftX, maxLeftY);
            }
        } else if (minRightX < maxLeftY) {
            low = partitionX + 1;
        } else {
            high = partitionX - 1;
        }
    }
    throw new RuntimeException();
}

总结

这道题如果能把图画出来，理解起来就很容易。但是这道题在LeetCode中的难度是hard，因为编写代码并不容易，有很多边界条件：
1. 数组长度的奇偶
2. 移动过程中，某个数组被切割后可能为空