Leetcode题解 4. Median of Two Sorted Arrays 【Array】

题目：

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)).

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

题意分析：
给出两个已经排好序的数组，求出他们的中位数


题目思路：

最笨的办法就是合并两个数组……然后sort，然后找中位数。O（nlogn）

第二笨的办法就是一个数一个数地合并两个数组，合并到中间就停止，返回答案。O（m+n）（m,n为两数组长度)

还有一种是二分搜索，时间复杂度是O(log (m+n)).（注：我自己没想到如何在两个数组中二分搜索，这是我看完讨论区高票答案后写的）：

联想到中位数的定义，我们把数组A分成两部分：

假设数组A有m个元素，则有m+1种分法。设左边元素个数为i，右边元素个数为m-i

对B也分成两部分：

假设数组B有n个元素，则有n+1种分法。设左边元素个数为j，右边元素个数为n-j

这样，我们就把两个数组各自分成两个部分：

如果我们能保证左边长度等于右边长度，并且A[i-1] <= b[j], B[j-1] <= A[i]，那么我们要找的中位数即是：

此时，我们设 i 为数组A左边长度，那么数组B的左边长度即为(m+n+1)/2 - i.这样我们就能保证左边长度总和等于右边

问题成为了找到一个i，使得B[j-1] <= A[i] && A[i-1] <= B[j]

这里， j = (m + n + 1)/(2) - i

实现二分查找：

先设定 i 的边界值为[imin, imax]; imin = 0, imax = m;

让 i = (imin + imax)/2, j = (m + n + 1)/2 - i

情况1：

B[j-1] <= A[i] && A[i-1] <= B[j]

说明找到了符合条件的i，停止二分搜索

情况2：

B[j-1] > A[i]

说明A[i]太小，由于数组都是按从小到大排序，那么我们需要增大 i 。

让imin = i+1

情况3：

A[i-1] > B[j]

说明A[i-1]太大，由于数组是按从小到大排序，我们需要减小 i。

让imax = i-1

AC代码：

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        m, n = len(nums1), len(nums2)
        if m > n:
            return self.findMedianSortedArrays(nums2, nums1)
        imin, imax, half = 0, m, (m + n + 1) // 2
        
        while imin <= imax:
            i = (imin + imax) // 2
            j = half - i
            if i < m and nums2[j - 1] > nums1[i]:
                imin = i + 1
            elif i > 0 and nums1[i - 1] > nums2[j]:
                imax = i - 1
            else:
                if i == 0:
                    max_left = nums2[j - 1]
                elif j == 0:
                    max_left = nums1[i - 1]
                else:
                    max_left = max(nums1[i - 1], nums2[j - 1])
                
                if (m + n) % 2 == 1:
                    return max_left
                
                if i == m:
                    min_right = nums2[j]
                elif j == n:
                    min_right = nums1[i]
                else:
                    min_right = min(nums1[i], nums2[j])
                
                return (max_left + min_right) / 2