题目

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

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

你可以假设 nums1 和 nums2 不会同时为空。

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