[4] Median of Two Sorted Arrays
Difficulty: Hard (33.87%)
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:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 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.
为了解决这个问题, 首先咱们将其合成为两个字问题
- 如何求两个数组中第 k 个数
- 如何计算中位数
如何求两个数组中第 k 个数
因为两个数组都是有序数组, 且题目要求咱们达到 log(m+n)的工夫复杂度, 所以应该尝试利用有序的个性, 应用二分的办法来解决这个问题
完结条件
如果一个数组空了, 两个数组的第 k 个数则为非空数组的第 k 个数
递归条件
如果两个数组均非空, 找到两个数组两头的数
如果 k 在 i1 和 i2 的右侧, 找出更小的那个, 截取后半段.
如果 k 在 i1 和 i2 的左侧, 找出更大的那个, 截取前半段.
def kth(l1, l2, k):
if not l1:
return l2[k]
if not l2:
return l1[k]
i1 = len(l1) // 2
i2 = len(l2) // 2
# 如果 k 在 i1、i2 的右侧
if i1 + i2 < k:
# 找出更小的那个,截取后半段
if l1[i1] < l2[i2]:
return kth(l1[i1 + 1:], l2, k - i1 - 1)
else:
return kth(l1, l2[i2 + 1:], k - i2 - 1)
else:
# k 在 i1、i2 的左侧,找出更大的那个,截取前半段
if l1[i1] < l2[i2]:
return kth(l1, l2[:i2], k)
else:
return kth(l1[:i1], l2, k)
如何计算中位数
如果数组为复数个元素, 找到第 (m+n)// 2 个数
如果数组为单数个元素, 找到第(m+n)// 2 个数和第(m+n)//2 – 1 个数, 求均匀即可
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
m = len(nums1)
n = len(nums2)
if (m + n) % 2 == 1:
return self.kth(nums1, nums2, (m + n) // 2)
else:
return (self.kth(nums1, nums2, (m + n) // 2) + self.kth(nums1, nums2, (m + n) // 2 - 1)
) / 2.0