Leetcode 4 Median of Two Sorted Arrays

发表于 |

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

题意分析:
在两个有序数组中寻找中位数，关键要求时间复杂度为0(log(m+n))
在第一次见到这个题的时候，我真是惊呆了，当时我还是个小白，没想到这道题居然能有这么巧妙的解法，光看懂答案就花了不知道多少时间。

思路分析：
我们知道中位数的定义是整个数组的最中间的数，换句话说，以中位数为界，可以将数组分为两个长度相等的部分。关键也就在此，例如对于两个有序数组，一个长度为3，一个长度5，那么我们知道按中位数划分后两边的数组长度应该都为4，并且满足左边数组的最大值要小于等于右边数组的最小值。

根据这个分析，我们只需要找出左边数组的4个数有几个是从第一个数组里面获得的即可。
例如我们假定左边数组的4个数中有i个数是从第一个数组中获得，那么则有4-i个数从第二个数组中获得。我们只需要判断 max(nums1[i-1], nums2[4-i-1])（左边数组的最大值）是否小于等于 min(nums1[i], nums1[4-i])（右边数组的最小值），如果满足上述式子，则说明我们成功找到了这个分界点，则中位数可求（要根据长度奇偶来分别计算）！

我们在寻找具体的i的时候使用二分法，由于i代表的意义为从第一个数组中拿多少数，所以i的最小值为0，最大值为 min(n, (m+n)//2)，所以是满足复杂度为0(log(m+n))这个条件的。

另一个关键点，我们知道二分法需要不停的变换上下界，那么在这里如果不满足上述条件，lo和hi应该怎样变化呢？关键在于nums[i-1]，如果是nums[i-1] > 右边的最小值，说明我们的i已经选的太大了，故hi = mid；反之，则说明我们的i选的太小了，导致4-i太大了，故lo = mid + 1。

当然在具体判断条件时可能会出现数组越界的情况，所以实际写代码的时候需要用到一点技巧来处理！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 68ms, beats 48.51%
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        n, m = len(nums1), len(nums2)
        t = (m+n) // 2
        l, r = 0, t
        inf = float('inf')
        while l <= r:
            # index1代表从nums1中拿的数量，index2代表从nums2中拿的数量
            # 若数组长度都不够拿的数量，就直接跳过
            index1 = (l+r) // 2
            if index1 > n:
                r = index1; continue
            index2 = t - index1
            if index2 > m:
                l = index1+1; continue
            # 处理数组越界的情况
            # 可能会出现一个都不从nums1里面拿，此时index1 = 0
            # 也或者nums1的所有数都要拿，此时 index1 = n
            l1 = nums1[index1-1] if 0 <= index1-1 < n else -inf
            r1 = nums1[index1] if 0 <= index1 < n else inf
            l2 = nums2[index2-1] if 0 <= index2-1 < m else -inf
            r2 = nums2[index2] if 0 <= index2 < m else inf

            # 满足条件后分奇偶进行计算
            if max(l1,l2) <= min(r1,r2):
                if (n+m) % 2 != 0: return min(r1,r2)
                return (max(l1,l2) + min(r1,r2)) / float(2)
            elif l1 > min(r1,r2):
                r = index1
            else:
                l = index1 + 1