[LeetCode] 4. Median of Two Sorted Arrays（Python）

• • 1. 题目
  • 2. 题目理解
  • 3. 代码实现

1. 题目

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Example 1:
Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Example 3:
Input: nums1 = [0,0], nums2 = [0,0] Output: 0.00000
Example 4:
Input: nums1 = [], nums2 = [1] Output: 1.00000
Example 5:
Input: nums1 = [2], nums2 = [] Output: 2.00000
Constraints:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

2. 题目理解

输入两个排好序的数组，返回两个数组的中位数，时间复杂度为O(log (m+n))。

3. 代码实现

1）思路一
将两个数组混为一个数组并排序，若共有偶数位，则取两个中间值的均值，否则输出中值。

class Solution(object):
	def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        m,n = len(nums1), len(nums2)
        nums = sorted(nums1 + nums2)
        med = int((m+n)/2)
        if (m+n)%2 == 0:
            return float(nums[med-1] + nums[med]) / 2
        else:
            return float(nums[med])

分析：使用了库函数sorted()，因此时间复杂度与此库函数有关。

2）思路二
引入寻找第k小的数的函数来避免一些冗余。在getKth()函数中，所有操作在第一个数组长度小于等于第二个的逻辑上产生。若第一个数组为空，则直接输出第二个数组的第k位。若k为1，则输出两个数组第一位中较小的数。k大于1时，对两个数组的k/2位开始比较，若A[k/2]较小，则比A[k/2]小的数最多有k-2个，所以A[k/2]前的数可以被放弃，操作的数组变为(A[k/2:], B, pb)，A[k/2]较大时想法类似，抛弃B数组后半部份的数。

class Solution(object):
    def getKth(self, A, B, k):
        lenA, lenB = len(A), len(B)
        if lenA > lenB: return self.getKth(B, A, k)
        if lenA == 0: return B[k - 1]
        if k == 1: return min(A[0], B[0])
        posi_a = min(k/2, lenA)
        posi_b = k - posi_a
        if A[posi_a - 1] <= B[posi_b - 1]:
            return self.getKth(A[posi_a:], B, posi_b)
        else:
            return self.getKth(A, B[posi_b:], posi_a)
    
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        len1, len2 = len(nums1), len(nums2)
        if (len1 + len2) % 2 == 1: 
            return self.getKth(nums1, nums2, (len1+len2)/2 + 1)
        else:
            return (self.getKth(nums1, nums2, (len1+len2)/2) + self.getKth(nums1, nums2, (len1+len2)/2 + 1)) * 0.5