题目描述
给定两个大小为 m 和 n 的有序数组 nums1
和 nums2
。
请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1
和 nums2
不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
解题思路
- 方法一:使用归并排序的思想,把两个数组排序后取中位数;
- 方法二:同方法一,但预先判断中位数的位置,可以提前终止排序。
- 方法三:二分法。具体题解见 LeetCode 官方题解。
代码
Python 3.6
方法一
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: res = [] p1, p2 = 0, 0 while p1 < len(nums1) and p2 < len(nums2): num1, num2 = nums1[p1], nums2[p2] if num1 <= num2: res.append(num1) p1 += 1 else: res.append(num2) p2 += 1 res += nums1[p1:] + nums2[p2:] mid = res[len(res) // 2] if len(res) % 2 == 1 else (res[len(res) // 2 - 1] + res[len(res) // 2]) / 2 return mid
|
执行用时 : 88 ms
内存消耗 : 13.3 MB
方法二
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: res = [] length = len(nums1) + len(nums2) size = length // 2 + 1 avg = True if length % 2 == 0 else False p1, p2 = 0, 0 while p1 < len(nums1) or p2 < len(nums2): if p1 >= len(nums1): res.append(nums2[p2]) p2 += 1 elif p2 >= len(nums2): res.append(nums1[p1]) p1 += 1 else: num1, num2 = nums1[p1], nums2[p2] if num1 <= num2: res.append(num1) p1 += 1 else: res.append(num2) p2 += 1 if len(res) == size: break mid = (res[-1] + res[-2]) / 2 if avg else res[-1] return mid
|
执行用时 : 84 ms
内存消耗 : 13.3 MB
方法三:二分法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: m, n = len(nums1), len(nums2) if n < m: nums1, nums2, m, n = nums2, nums1, n, m i_min, i_max = 0, m while i_min <= i_max: i_mid = (i_min + i_max) // 2 j = (m + n + 1) // 2 - i_mid if i_mid > 0 and nums1[i_mid - 1] > nums2[j]: i_max = i_mid - 1 elif i_mid < m and nums2[j - 1] > nums1[i_mid]: i_min = i_mid + 1 else: if i_mid == 0: max_left = nums2[j - 1] elif j == 0: max_left = nums1[i_mid - 1] else: max_left = max(nums1[i_mid - 1], nums2[j - 1]) if (m + n) % 2 == 1: return max_left if i_mid == m: min_right = nums2[j] elif j == n: min_right = nums1[i_mid] else: min_right = min(nums1[i_mid], nums2[j]) return (max_left + min_right) / 2
|
执行用时: 76 ms
内存消耗: 13.4 MB