Median of two Sorted Arrays

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

这题最直接的思路就是按 merge two sorted array 的办法，数出来一半的数字。但是那个时间复杂度是 O(m + n)。题目要求 O(log(m+n))

第一个思路是看了九章来的。先看截图

做法就是在 A, B 两数组中各取第 k/2 个数，比一下 ，小的那边就把所有那个位置之前的数都淘汰了。corner case 就是如果某个数组中（比如说 A[]）剩下的数不足 k/2 咋办？直接扔掉另外一边的数(B[])。因为即使A[]里面剩下的数都比 B 里的小，因为不足 k/2 个，被扔掉的 B 里面的 k/2 个数肯定不会是总体第 k 位的数。

时间复杂度 O(log(m+n))。程序：

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        length = len(nums1) + len(nums2)
        if length % 2 == 1:
            return self.findKth(nums1, 0, nums2, 0, (length + 1) // 2) * 1.0
        else:
            return (self.findKth(nums1, 0, nums2, 0, length // 2)
                   + self.findKth(nums1, 0, nums2, 0, length // 2 + 1)) / 2.0



    def findKth(self, A, idxA, B, idxB, k):
        if k == 1:
            if idxA >= len(A):
                return B[idxB]
            elif idxB >= len(B):
                return A[idxA]
            else:
                return min(A[idxA], B[idxB])

        offset = k // 2 - 1
        if idxA + offset >= len(A):
            return self.findKth(A, idxA, B, idxB + offset + 1, k - k // 2)
        elif idxB + offset >= len(B):
            return self.findKth(A, idxA + offset + 1, B, idxB, k - k // 2)
        elif A[idxA + offset] < B[idxB + offset]:
            return self.findKth(A, idxA + offset + 1, B, idxB, k - k // 2)
        else:
            return self.findKth(A, idxA, B, idxB + offset + 1, k - k // 2)

第二个思路的时间复杂度没有达到要求，但是能 AC，时间复杂度 O(log(range)∗(log(n)+log(m)))

思路就是对值二分。程序如下。但是二分比较tricky，想了一阵才明白，在这样的写法下，为什么 二分出来的数值， 肯定是两数组中的某一个数。只能背下来了。 while lo < hi ... if count >= k hi = mid else lo = mid + 1

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        length = len(nums1) + len(nums2)
        if length % 2 == 1:
            return self.findKth(nums1, nums2, (length + 1) // 2) * 1.0
        else:
            return (self.findKth(nums1, nums2, length // 2)
                   + self.findKth(nums1, nums2, length // 2 + 1)) / 2.0



    def findKth(self, A, B, k):
        if not A:
            return B[k - 1]
        elif not B:
            return A[k - 1]

        lo, hi = min(A[0], B[0]), max(A[-1], B[-1])

        while lo < hi:                                 # 死记硬背
            mid = (lo + hi) // 2                       #
            if self.countLessEqual(A, B, mid) >= k:    #
                hi = mid                               #
            else:                                      #
                lo = mid + 1                           #

        return lo

    def countLessEqual(self, A, B, value):    # 算小于等于 value 的元素的个数
        import bisect
        return bisect.bisect(A, value) + bisect.bisect(B, value)

第三个方法是最好的，有视频教程：https://www.youtube.com/watch?v=LPFhl65R7ww

文字解释：https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2481/

时间复杂度 O( log( min(m,n) ) )

来张截图

思路就是，短的数组为x，长的数组为y，在x中切一刀，相应的在一种切一刀。然后比较大小看是不是切对了，不对的话二分下一个下刀的位置。

程序

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        import sys
        if len(nums1) == 0 and len(nums2) == 0:
            return 0

        m, n = len(nums1), len(nums2)

        if m > n:
            return self.findMedianSortedArrays(nums2, nums1)

        lo, hi = 0, m

        while lo <= hi:
            cutIdx1 = (lo + hi) // 2
            cutIdx2 = (m + n + 1) // 2 - cutIdx1

            if cutIdx1 == 0:
                maxLeft1 = nums2[cutIdx2 - 1]
            else:
                maxLeft1 = nums1[cutIdx1 - 1]

            maxLeft1 = -sys.maxint - 1 if cutIdx1 == 0 else nums1[cutIdx1 - 1]   # 这几行是为了处理 corner cases
            maxLeft2 = -sys.maxint - 1 if cutIdx2 == 0 else nums2[cutIdx2 - 1]   #
            minRight1 = sys.maxint if cutIdx1 == m else nums1[cutIdx1]           #
            minRight2 = sys.maxint if cutIdx2 == n else nums2[cutIdx2]           #

            if maxLeft1 > minRight2:
                hi = cutIdx1 - 1
            elif maxLeft2 > minRight1:
                lo = cutIdx1 + 1
            else:
                ## maxLeft1 <= minRight2 and maxLeft2 <= minRight1. Found solution
                if (m + n) % 2 == 1:
                    return max(maxLeft1, maxLeft2) * 1.0
                else:
                    return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2) ) / 2.0

            print lo, hi

        return 0