[LeetCode]4. 寻找两个有序数组的中位数(Median of Two Sorted Arrays)

题目描述

给定两个大小为 m 和 n 的有序数组 nums1nums2
请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1nums2 不会同时为空。

示例 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