4.Median of Two Sorted Arrays

Tags: [sort], [divide_conquer], [trick]

Com: {g}

Hard: [####]

Link: https://leetcode.com/problems/median-of-two-sorted-arrays/\#/description

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

Solution: Divide And Conquer, Trick

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        size1, size2 = len(nums1), len(nums2)
        left_k = (size1 + size2 + 1) / 2
        right_k = (size1 + size2 + 2) / 2
        return (self.get_k_smallest_elem(nums1, 0, nums2, 0, left_k) +
                self.get_k_smallest_elem(nums1, 0, nums2, 0, right_k)) / 2.0

    def get_k_smallest_elem(self, nums1, start1, nums2, start2, k):
        # base case
        if start1 >= len(nums1):
            return nums2[start2 + k - 1]
        if start2 >= len(nums2):
            return nums1[start1 + k - 1]
        if k == 1:
            return min(nums1[start1], nums2[start2])

        mid1, mid2 = sys.maxint, sys.maxint
        if start1 + k / 2 - 1 < len(nums1):
            mid1 = nums1[start1 + k / 2 - 1]
        if start2 + k / 2 - 1 < len(nums2):
            mid2 = nums2[start2 + k / 2 - 1]
        if mid1 < mid2:
            # the next step will check nums1[right part] + nums2[left part]
            return self.get_k_smallest_elem(nums1, start1 + k / 2, nums2, start2, k - k / 2)
        else:
            # the next step will check nums2[right part] + nums1[left part]
            return self.get_k_smallest_elem(nums1, start1, nums2, start2 + k / 2, k - k / 2)

Revelation:

• k is based on 1.

Note:

• Time complexity = O(lg(size1 + size2)), size1 is the number of elements in nums1, size2 is the number of elements in nums2.