Leetcode 4. Median of Two Sorted Arrays

https://leetcode.com/problems/median-of-two-sorted-arrays/

这道题的题意是给定两个已经排好序的数组,求这两个数组所有数字的中位数,要求时间复杂度是O(log(m+n))的(应该自然想到
是二分法)

这道题感觉有点难,看了半天代码也看不懂是什么意思。。。,不过这样的题确实有意思。。。

思路: 在两个数组中找两个分解点i,j,保证0~i-1加0~j-1是两个数组的长度之和的一半,目标就是确定i和j的位置,使得
i-1位置数字也小于j位置数字(i-1位置数字保证小于i位置数字)和j-1位置数字小于i位置数字,这样0~i-1和0~j-1位置所有
数字都小于另一半部分的数字,中位数就是i-1和j-1位置数字的较大值和i位置和j位置数字的较小值的均值(两个数组所有数字
个数是偶数的话),或者i-1和j-1位置数字的较大值

代码:

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
if(m > n)
return findMedianSortedArrays(nums2, nums1);

int left = 0, right = m;
int i = -1, j = -1;
while(true){
i = (left + right) / 2;
j = (m + n + 1) / 2 - i;

if((i == 0 || j == n || nums1[i - 1] <= nums2[j]) &&
(j == 0 || i == m || nums2[j - 1] <= nums1[i])){
break;
}
else if(i > 0 && nums1[i-1] > nums2[j]){
right = i - 1;
}
else if(j > 0 && nums2[j-1] > nums1[i]){
left = i + 1;
}
}

int max_left = -1, min_right = -1;
if(i == 0){
max_left = nums2[j-1];
}
else if(j == 0){
max_left = nums1[i-1];
}
else{
max_left = max(nums1[i - 1], nums2[j - 1]);
}

if((m+n) % 2){
return max_left;
}

if(i == m)
min_right = nums2[j];
else if(j == n)
min_right = nums1[i];
else{
min_right = min(nums1[i], nums2[j]);
}

return double(max_left + min_right) / 2;
}
};

0%