喜欢y大教的二分模板来做
以A、B两串最短的为A串 求分界处 使得分界右侧的点均大于等于左侧 最后求得l=r 表示A中有r个元素在前n/2中
当总个数为奇数时 需要考虑1.当r=0时应该使得中位数直接为B中第k个元素,k表示中位数的序号即最终排序序列第
几个元素
2.当A B两串长度相同(偶)且r=k时 A[k-1]
3.最后正常情况只需求得A[i-1] B[j-1]中最大值为中位数
上面时是奇数情况 当然也包括偶数的一边 现在求另一边 正常情况只需考虑 A[r] 时是奇数情况 当然也包括偶数的一边
现在求另一边 正常情况只需考虑 A[r] 和 B[k-r]中最小值,但是当r==0 && k==B.length时 只能考虑A[0],烦人的就是
还要考虑 r==A.length时 只考虑B[k-r]
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
int[] Anums = len1<=len2?nums1:nums2;
int[] Bnums = len1>len2?nums1:nums2;
len1 = Anums.length;
len2 = nums1.length + nums2.length - len1;
int l, r, k;
l = 0; r = len1;
double ans = 0;
k = len1 + len2 + 1 >> 1;//中间值
while(l<r){
int mid = l + r >> 1;
int j = k - mid;
if(mid<len1&&Anums[mid]>=Bnums[j-1]) r = mid;
else l = mid + 1;
if(mid==len1){
l = r;
break;
}
}
//考虑的边界情况 TMD 这里对应上面解释
if(r==0) ans = Bnums[k-1];
else if(r==k) ans = Anums[k-1];
else ans = Math.max(Anums[r-1], Bnums[k-r-1]);
if((len1+len2&1)==1) return ans;//奇数情况
if(r==0&&k==len2) ans += Anums[0];
else if(r<len1) ans += Math.min(Anums[r], Bnums[k-r]);
else ans += Bnums[k-r];
return ans/2;
}
}