0%

LeetCode 4.寻找两个有序数组的中位数

给定两个大小为 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

ac

简单解析:最重要的就是求两个有序数组中的第k大,有几个小细节注意一下就行了。
如,求两个有序数组$A$和$B$的第$K$大的数,那么将$A$和$B$的前$\frac{K}{2}$的数组分别切割出来,比较$A[\frac{K}{2}]$和$B[\frac{K}{2}]$的大小就可以消去$\frac{K}{2}$个数,为什么那?因为如果$A[\frac{K}{2}]<B[\frac{K}{2}]$,那么$A[0:\frac{K}{2}]$肯定都小于$B[\frac{K}{2}]$(废话),所以接下来只需要在剩下的数中找第$\frac{K}{2}$大的数就行了(一些细节没描述),详见代码。
时间复杂度:$O(log_{2}{(len(A)+len(B)}))$

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:
double findkth(vector<int>& nums1, vector<int>& nums2, int l1, int r1, int l2, int r2, int k) {
if (l1 > r1) return nums2[l2 + k -1]; // 如果nums1空了,return nums2的第k个,下同理
if (l2 > r2) return nums1[l1 + k -1];
if (k == 1) return min(nums1[l1], nums2[l2]); // 因为最后一次比较后肯定是前k个比较完了,l1和r1一个是在前k个,一个不是
// 前k个,答案是第k个,是小的那个,所以取min()
int mid = k / 2; // 如果是奇数就向下取整
int new1 = l1 + mid - 1, new2 = l2 + mid -1;
if (new1 > r1) new1 = r1; // 当溢出时让new1=r1,不影响结果,只是令log2不太log2而已
if (new2 > r2) new2 = r2;
if (nums1[new1] < nums2[new2]) {
return findkth(nums1, nums2, new1 + 1, r1, l2, r2, k - (new1 - l1 + 1));
} else {
return findkth(nums1, nums2, l1, r1, new2 + 1, r2, k - (new2 - l2 + 1));
}
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len1 = nums1.size(), len2 = nums2.size();
if ((len1 + len2) & 1) {
return findkth(nums1, nums2, 0, len1 - 1, 0, len2 - 1, (len1 + len2 + 1) / 2);
}
double ans = findkth(nums1, nums2, 0, len1 - 1, 0, len2 - 1, (len1 + len2) / 2);
ans += findkth(nums1, nums2, 0, len1 - 1, 0, len2 - 1, (len1 + len2) / 2 + 1);
ans /= 2;
return ans;
}
};