题目描述
给定两个大小为 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