有两个长度分别为n和m的有序数组,计算这2个数组中所有元素的中位数。
如果元素个数为偶数,那么中位数为中间2个元素之和除以2(向下取整)。
样例1:
arr1: [1, 4, 5] arr2: [2, 3] 应该返回3。
样例2:
arr1: [1, 7, 8] arr2: [2, 3, 6] 应该返回4((3+6) / 2=4)。
提示:1. 使用O(log(m+n))的算法;
2. 尝试多种方法。
写过好多回了,还是没有一次写对,哎,注意在getVal里对a.empty()时候的处理。
const int INT_MIN=-100000000; const int INT_MAX=100000000; int findMedian(vector<int>& a,int l,int r,vector<int>& b); int getVal(vector<int>& a,int k); int median(vector<int> &arr1, vector<int> &arr2) { if ( arr1.empty()&&arr2.empty() ) return 0; if ( arr1.size() >= arr2.size() ) return findMedian(arr1,0,arr1.size()-1,arr2); else return findMedian(arr2,0,arr2.size()-1,arr1); } int findMedian(vector<int>& a,int l,int r,vector<int>& b) { int na=a.size(),nb=b.size(); if ( l> r) return findMedian(b,max(0,(na+nb)/2-na),min(nb-1,(na+nb)/2),a); int mid=(l+r)>>1; int less=(na+nb)/2-mid-1; if (getVal(b,less)>a[mid]) return findMedian(a,mid+1,r,b); else if (getVal(b,less+1)<a[mid] ) return findMedian(a,l,mid-1,b); else { if ( (na+nb)&1 ) return a[mid]; else return (max(getVal(a,mid-1),getVal(b,less))+a[mid])/2; } } int getVal(vector<int>& a,int k) { if ( a.empty() ) return k<0?INT_MIN:INT_MAX; if (k<0) return INT_MIN; else if (k>=a.size()) return INT_MAX; else return a[k]; }