首页 > 代码库 > [LeetCode]Median of Two Sorted Arrays查找第k数(中位数)
[LeetCode]Median of Two Sorted Arrays查找第k数(中位数)
二分。情况讨论
class Solution { public: int findPos(int* p,int n,int x){ int low=0,high=n-1,mid; while(low<=high){ mid=(low+high)>>1; if(p[mid]<=x)low=mid+1; else high=mid-1; } return low; } double findK(int a[], int m, int b[], int n,int k){ int mid1,mid2,low1=0,low2=0,high1=m-1,high2=n-1,x; while(low1<=high1&&low2<=high2){ mid1=(high1+low1)>>1; mid2=(high2+low2)>>1; if(a[mid1]<b[mid2]){ if(mid1+mid2+2==k){ low1=mid1+1; high2=mid2; } else if(mid1+mid2+2<k){ low1=mid1+1; } else high2=mid2-1; } else{ if(mid1+mid2+2==k){ low2=mid2+1; high1=mid1; } else if(mid1+mid2+2<k){ low2=mid2+1; } else high1=mid1-1; } } if(low1<=high1){ // if(low1==high1)return a[low1]; while(low1<=high1){ mid1=(low1+high1)>>1; x=findPos(b,n,a[mid1]); if(x+mid1+1==k)return a[mid1]; else if(x+mid1<k)low1=mid1+1; else high1=mid1-1; } return low1>=m?a[m-1]:a[low1]; } else { // if(low2==high2)return b[low2]; while(low2<=high2){ mid2=(low2+high2)>>1; x=findPos(a,m,b[mid2]); if(x+mid2+1==k)return b[mid2]; else if(x+mid2<k)low2=mid2+1; else high2=mid2-1; } return low2>=n?a[n-1]:b[low2]; } } double findMedianSortedArrays(int a[], int m, int b[], int n) { int k=m+n; if(k&1){ return findK(a,m,b,n,k/2+1); } else{ return (findK(a,m,b,n,k/2)+findK(a,m,b,n,k/2+1))/2.0; } } };
[LeetCode]Median of Two Sorted Arrays查找第k数(中位数)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。