Median of 2 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)).

解题方法

brute force

count sort, 时间复杂度不符合要求

二分法

general的问题是，两个sorted array,找第k个，对于median这道题，k就是总长度。 还要注意k的奇偶性：

• k是偶数，就是找第k/2个
• k是奇数，就是算第k/2个和第k/2+1个的平均值

在具体findKth的function中，

1. 如果某一个array为空，直接在另一个array中取第k个。

2. 如果某一个array的长度小于k/2，就可以去掉每次另一个array的前k/2个

3. 如果长度都大于k/2, 分别取k/2个，比较大小，可以按情况去掉两个array的一部分

要注意k的奇偶性的影响，对大的array的部分应该取nums[:k/2+1],因为k是奇数的 话应该返回k/2 + k/2 + 1个，要将nums[k/2]包含

比较大小

Solution

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        total_length = len(nums1) + len(nums2)
        if total_length % 2 == 1: # odd
            return self.findKth(nums1, nums2, total_length / 2 + 1)
        else:
            # even, pick two and average them
            smaller = self.findKth(nums1, nums2, total_length / 2)
            bigger = self.findKth(nums1, nums2, total_length / 2 + 1)
            return (smaller + bigger) / 2.0

    def findKth(self, nums1, nums2, k):
        if len(nums1) == 0:
            return nums2[k-1]
        if len(nums2) == 0:
            return nums1[k-1]
        if k == 1:
            return min(nums1[0], nums2[0])

        if len(nums1) < k / 2:
            mid_1 = "short"
        else:
            mid_1 = nums1[k/2 - 1]

        if len(nums2) < k / 2:
            mid_2 = "short"
        else:
            mid_2 = nums2[k/2 - 1]

        if mid_1 == "short":
            return self.findKth(nums1, nums2[k/2:], k - k/2)
        if mid_2 == "short":
            return self.findKth(nums1[k/2:], nums2, k - k/2)
        if mid_1 < mid_2:
            return self.findKth(nums1[k/2:], nums2[:k/2+1], k - k/2) # 注意index
        elif mid_1 >= mid_2:
            return self.findKth(nums1[:k/2+1], nums2[k/2:], k - k/2) # 注意index

Reference