leetcode-寻找两个正序数组的中位数

点击:题目链接:给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

思路

一种思路就是使用双指针,不断找到大数组的中位数,但是要注意的是,个数有奇偶之分

另一种思路,直接利用中位数:

  1. 为了避免奇偶性的判断,我们也可以先将大数组填充为之前的两倍,保证个数肯定是双数。
  2. 填充后,两个数组的中位数与大数组的关系就为,center1 +center2 = m+n
  3. 使用两个数组的中位数与合并后大数组的关系 l1 < r2 && l2 < r1, l,r 分别是对应数组的中位数的相邻两个元素
  4. 当其中大数组的中位数只出现在一个数组,说明此时另一个数组的数比当前的数组的数都要大或小,临界值可以表示为
    • center1 == 0, l1 = INT_MAX
    • cetner1 == m, r1 = INT_MIN
    • center2 == 0, l2 = INT_MAX
    • cetner2 == n, r2 = INT_MIN

代码

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) {
if(nums1.size() > nums2.size()) return findMedianSortedArrays(nums2, nums1);

int n = nums1.size();
int m = nums2.size();

int l1, r1, l2, r2, c1,c2,low = 0, high = 2*n;

while(low<=high){

//扩充之后的中位线
c1 = (low+high)/2;
c2 = m+n -c1;

l1 = (c1 ==0)? INT_MIN:nums1[(c1-1)/2];
r1 = (c1 == 2*n)? INT_MAX: nums1[(c1)/2];

l2 = (c2==0)? INT_MIN:nums2[(c2-1)/2];
r2 = (c2 == 2*m)?INT_MAX:nums2[(c2)/2];

if(l1>r2){
high = c1-1;
}else if(l2>r1){
low = c1+1;
}else{
break;
}
}

return (max(l1,l2)+ min(r1,r2))/2.0;
}
};

复杂度

时间O(log(min(m,n))),空间(1)

作者

Dylan Zhu

发布于

2021-04-11

更新于

2021-04-11

许可协议

评论

:D 一言句子获取中...