题目

给定两个大小为 m 和 n 的正序(从小到大)数组 nums1nums2

请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1nums2 不会同时为空。

示例 1:

1
2
3
4
nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2:

1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5
  • 数组
  • 二分查找
  • 分治算法

解法

由于指定了时间复杂度,所以不能采用普通的排序算法。

遍历

同时遍历两个数组,然后比对每一个取出的数,小的则加入到结果数组中,同时索引往后+1,继续取数比较,直到其中一个数组遍历结束,则将未结束的部分加到结果数组中。然后取中位数。

  • 时间复杂度:$O(m,n)=min(m, n)$
  • 空间复杂度:$O(m,n)=m+n$
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
31
32
33
34
35
36
class Solution:
def findMedianSortedArrays(self, nums1, nums2) -> float:
idx1 = 0
idx2 = 0
tmpL = []
while idx1 < len(nums1) or idx2 < len(nums2):
if idx1 < len(nums1):
num1 = nums1[idx1]
else:
tmpL += nums2[idx2:]
break
if idx2 < len(nums2):
num2 = nums2[idx2]
else:
tmpL += nums1[idx1:]
break

if num1 < num2:
tmpL.append(num1)
idx1 += 1
elif num1 > num2:
tmpL.append(num2)
idx2 += 1
else:
tmpL.append(num1)
tmpL.append(num2)
idx1 += 1
idx2 += 1
if len(tmpL) % 2:
return tmpL[len(tmpL)//2]

else:
return sum([tmpL[len(tmpL)//2], tmpL[len(tmpL)//2-1]])/2

# runtime:68 ms
# memory:13.6 MB

二分法

两个数组同时二分,分别将各种的两组进行分对,直到不可再分。

  • 时间复杂度:$O(n)=$
  • 空间复杂度:$O(n)=$
1
2