问题描述
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
示例 3：
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
示例 4：
输入：nums1 = [], nums2 = [1]
输出：1.00000
示例 5：
输入：nums1 = [2], nums2 = []
输出：2.00000
提示：
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
解题思路
方法一：排序（通过）
最简单的方法就是合并两个数组后排序。
时间复杂度：\(\mathcal{O}((m+n)\log(m+n))\)
空间复杂度：\(\mathcal{O}(\min(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: List[int], nums2: List[int]) -> float:
n1, n2 = len(nums1), len(nums2)
L, R = (n1 + n2 - 1) // 2, (n1 + n2) // 2
x = y = k = 0
while nums1 and nums2:
if nums1[-1] >= nums2[-1]:
mx = nums1.pop()
else:
mx = nums2.pop()
if k == L:
x = mx
if k == R:
y = mx
k += 1
while nums1:
if k == L:
x = nums1[-1]
if k == R:
y = nums1[-1]
nums1.pop()
k += 1
while nums2:
if k == L:
x = nums2[-1]
if k == R:
y = nums2[-1]
nums2.pop()
k += 1
return (x + y) / 2
|
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 | class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n1 = nums1.size(), n2 = nums2.size();
int L = (n1 + n2 - 1) / 2, R = (n1 + n2) / 2;
int x, y;
int i = 0, j = 0, k, mn;
while (i < n1 && j < n2) {
k = i + j;
if (nums1[i] <= nums2[j]) {
mn = nums1[i++];
} else {
mn = nums2[j++];
}
if (k == L) x = mn;
if (k == R) y = mn;
}
while (i < n1) {
if (i + j == L) x = nums1[i];
if (i + j == R) y = nums1[i];
++i;
}
while (j < n2) {
if (i + j == L) x = nums2[j];
if (i + j == R) y = nums2[j];
++j;
}
return (x + y) / 2.0;
}
};
|
时间复杂度：\(\mathcal{O}(n)\)
空间复杂度：\(\mathcal{O}(1)\)
方法三：二分搜索（通过）
关键在于确定每个数在两个数组中合并后的位置范围。
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:
def findKth(s1: List[int], s2: List[int], k: int) -> int:
L, R = 0, len(s2) - 1
while L <= R:
M = L + ((R - L) >> 1)
a, b = bisect_left(s1, s2[M]) + M, bisect_right(s1, s2[M]) + M
if k < a: R = M - 1
elif k > b: L = M + 1
else: return s2[M]
return findKth(s2, s1, k)
n = len(nums1) + len(nums2)
return (findKth(nums1, nums2, (n - 1) // 2) + findKth(nums1, nums2, n // 2)) / 2.0
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | class Solution {
public:
int findKth(vector<int> &s1, vector<int> &s2, int k) {
int L = 0, R = s2.size() - 1;
while (L <= R) {
auto M = L + ((R - L) >> 1);
auto range = equal_range(s1.begin(), s1.end(), s2[M]);
int a = range.first - s1.begin() + M, b = range.second - s1.begin() + M;
if (k < a) R = M - 1;
else if (k > b) L = M + 1;
else return s2[M];
}
return findKth(s2, s1, k);
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size() + nums2.size();
return (findKth(nums1, nums2, (n - 1) / 2) + findKth(nums1, nums2, n / 2)) / 2.0;
}
};
|
时间复杂度：\(\mathcal{O}(\log(m)\log(n))\)
空间复杂度：\(\mathcal{O}(1)\)
方法四：二分搜索（通过）
从方法三中可以看出，可以直接判断 \(\texttt{s2}[M]\) 能否作为第 \(k\) 个数。
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 | class Solution {
public:
int findKth(vector<int> &s1, vector<int> &s2, int k) {
// 查找合并后的第 k 个数（从 1 开始）
int n1 = s1.size(), n2 = s2.size();
if (n1 == 0) return s2[k - 1];
if (n2 == 0) return s1[k - 1];
int L = 0, R = min(k - 1, n2 - 1);
while (L <= R) {
auto M = L + ((R - L) >> 1); // 在 s2 中包含 M + 1 个数
if (M + 1 == k) {
if (s1[0] >= s2[M]) return s2[M]; // s2[M] 刚好是 s2 中的第 k 个数，而且可以将 s1 中的数全部放在 s2[M] 之后，即 s2[M] 可以是合并后的第 k 个数
break;
}
int pos = k - M - 1 - 1; // 在 s1 中包含 k - (M + 1) 个数，所以下标为 k - (M + 1) - 1
if (pos >= n1 || s1[pos] > s2[M]) L = M + 1; // 不够 k 个数
else if (s1[pos] <= s2[M] && (pos + 1 >= n1 || s1[pos + 1] >= s2[M])) return s2[M]; // s1[pos] 及之前的数可以放在 s2[M] 之前，而且 s1[pos] 之后的数可以放在 s2[M] 之后，所以 s2[M] 可以作为合并后的第 k 个数
else R = M - 1; // s1[pos + 1] < s2[M]，超过 k 个数
}
return findKth(s2, s1, k); // 第 k 个数不在 s2 中
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size() + nums2.size();
return (findKth(nums1, nums2, (n - 1) / 2 + 1) + findKth(nums1, nums2, n / 2 + 1)) / 2.0;
}
};
|
时间复杂度：\(\mathcal{O}(\log(m) + \log(n))\)
空间复杂度：\(\mathcal{O}(1)\)