[LeetCode] 4. Median of Two Sorted Arrays（Python）
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