思路蛮简单的 一看就是二分的问题 但是处理种种细节 各种边界条件…奇偶数判断等等…
自己写出了种种问题…还是看了看官方题解…牛（
++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
| class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
vector<int> *num1=&nums1,*num2=&nums2;
if(nums1.size()>nums2.size()){
swap(num1,num2);
}
vector<int> &A=*num1,&B=*num2;
int m=num1->size(),n=num2->size();
int iMin=0,iMax=m,halflen=(m+n+1)/2;
while(iMin<=iMax){
int i=(iMin+iMax)/2;
int j=halflen-i;
if(i<iMax&&B[j-1]>A[i]){
iMin=i+1;
}else if(i>iMin&&A[i-1]>B[j]){
iMax=i-1;
}else{
int maxLeft = 0;
if (i == 0) { maxLeft = B[j-1]; }
else if (j == 0) { maxLeft = A[i-1]; }
else { maxLeft = max(A[i-1], B[j-1]); }
if ( (m + n) % 2 ) { return maxLeft; }
int minRight = 0;
if (i == m) { minRight = B[j]; }
else if (j == n) { minRight = A[i]; }
else { minRight = min(B[j], A[i]); }
double tmp=maxLeft+minRight;
return tmp/ 2.0;
}
}
return 0;
}
};
|