LeetCode median-of-two-sorted-arrays

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

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

你可以假设 nums1 和 nums2 不会同时为空。 示例 1:

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

则中位数是 2.0

示例 2:

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

则中位数是 (2 + 3)/2 = 2.5

解答:

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
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
int m = nums2.size();

if (n > m) {
return findMedianSortedArrays(nums2, nums1);
}

int Lmax1, Lmax2, Rmin1, Rmin2, c1, c2, st = 0, ed = 2 * n;
// 方便奇偶处理,用2n代替n
while (st <= ed) {
c1 = (st + ed) / 2;
c2 = n + m - c1;

Lmax1 = (c1 == 0) ? INT_MIN : nums1[(c1 - 1) / 2];
Lmax2 = (c2 == 0) ? INT_MIN : nums2[(c2 - 1) / 2];
Rmin1 = (c1 == 2 * n) ? INT_MAX : nums1[c1 / 2];
Rmin2 = (c2 == 2 * m) ? INT_MAX : nums1[c2 / 2];

if (Lmax1 > Rmin2) {
ed = c1 - 1;
} else if (Lmax2 > Rmin1) {
st = c1 + 1;
} else {
break;
}
}
return (max(Lmax1, Lmax2) + min(Rmin1, Rmin2)) / 2.0;
}
};

提示:数组的中位数即中位数左边的数都小于右边的数。最容易的的方法就是合并数组,排序。取中间的数,但是不满足时间复杂度要求。继而想到不合并数组,分别取两个数组的中位数,并调整(左移,右移)中位数的位置,使得两个数组中位数左边的数都小于右边的数,又因为数组总长度一定,两个中位数取一个就可以知道另一个的位置,所以只需遍历一次即可,而后时间复杂都要求中有 log,所以将遍历改为二分法查找。

参考解析

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×