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

对列表的操作

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        nums1.extend(nums2)
        lst = sorted(nums1)

        if len(lst)%2==1:
            return lst[len(lst)//2]
        else:
            return (lst[len(lst)//2]+lst[len(lst)//2-1])/2.0

不能那么直接的sorted了，上二分法：

class Solution:
    def findMedianSortedArrays(self, A: 'List[int]', B: 'List[int]') -> 'float':
        l = len(A) + len(B)
        if l % 2 == 1:
            return self.kth(A, B, l // 2)
        else:
            return (self.kth(A, B, l // 2) + self.kth(A, B, l // 2 - 1)) / 2.   

    def kth(self, a, b, k):
        if not a:
            return b[k]
        if not b:
            return a[k]
        ia, ib = len(a) // 2 , len(b) // 2
        ma, mb = a[ia], b[ib]

        # when k is bigger than the sum of a and b's median indices
        if ia + ib < k:
            # if a's median is bigger than b's, b's first half doesn't include k
            if ma > mb:
                return self.kth(a, b[ib + 1:], k - ib - 1)
            else:
                return self.kth(a[ia + 1:], b, k - ia - 1)
        # when k is smaller than the sum of a and b's indices
        else:
            # if a's median is bigger than b's, a's second half doesn't include k
            if ma > mb:
                return self.kth(a[:ia], b, k)
            else:
                return self.kth(a, b[:ib], k)

再来一个最牛逼的算法，算法复杂度为 1O(log(min(M,N))):

class Solution:
    def findMedianSortedArrays(self, nums1: 'List[int]', nums2: 'List[int]') -> 'float':
        N1, N2 = len(nums1), len(nums2)
        if N1 < N2:
            nums1, N1, nums2, N2 = nums2, N2, nums1, N1
        l, r = 0, N2*2
        while l <= r:
            j = (l + r) >> 1
            i = N1 + N2 - j
            L1 = float('-inf') if i == 0 else nums1[(i-1)>>1]
            L2 = float('-inf') if j == 0 else nums2[(j-1)>>1]
            R1 = float('inf') if i == 2*N1 else nums1[i>>1]
            R2 = float('inf') if j == 2*N2 else nums2[j>>1]
            if L1 > R2: l = j + 1
            elif L2 > R1: r = j - 1
            else:
                return (max(L1, L2) + min(R1, R2))/2

再来一个stefan大大的算法，自制的二分查找：

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        a, b = sorted((nums1, nums2), key=len)
        m, n = len(a), len(b)
        after = (m + n - 1) // 2
        lo, hi = 0, m
        while lo < hi:
            i = (lo + hi) // 2
            if after-i-1 < 0 or a[i] >= b[after-i-1]:
                hi = i
            else:
                lo = i + 1
        i = lo
        nextfew = sorted(a[i:i+2] + b[after-i:after-i+2])
        return (nextfew[0] + nextfew[1 - (m+n)%2]) / 2.0

再来一个自制的算法：

1. 先对两个数组求逆；
2. 每次pop出最后一个元素比较，小的元素放到目标列表中。
3. 再来判断哪个列表为空，把不为空的别表求逆序，然后放入目标队列末尾
4. 求中位数。

完全就是 merge 2 sorted array 的方法，加上最后的求中位数的方法。和第21题有点类似。

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        d = list()

        s1 = nums1[::-1]
        s2 = nums2[::-1]

        while s2 and s1:
            if s1[-1] >= s2[-1]:
                d.append(s2.pop())
            elif s1[-1] < s2[-1]:
                d.append(s1.pop())
        d.extend(s1[::-1]) if not len(s2) else d.extend(s2[::-1])
        if len(d) % 2:
            return d[len(d)//2]
        else:
            return (d[len(d)//2] + d[len(d)//2 - 1]) /2