您当前位置：首页 > 互联网 > Median of Two Sorted Arrays

Median of Two Sorted Arrays

来源：程序员人生发布时间：2014-11-03 08:23:24 阅读次数：2597次

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

题意：寻觅两个有序数组的中位数，要求复杂度为O(log (m+n)).
思路：问题本质其实就是求两个有序数组的第Kth的数，那末我们可以这样斟酌，分别求出a,b两个数组中第k/2th的数，这两个数有3种情况

当a[k/2]<b[k/2]时，那末原kth数肯定不在a[k/2]之前的数内，然后抛弃a[k/2]之前的所有数，再在剩余的数里求k-(k/2)th数，其余两种情况同理，递归2分，所以复杂度降到对数级别

double find_kth(int a[],int m,int b[],int n,int k){ if(m>n) return find_kth(b,n,a,m,k); if(m==0) return b[k⑴]; if(k==1) return min(a[0],b[0]); int pa=min(k/2,m),pb=k-pa; if(a[pa⑴]<b[pb⑴]) return find_kth(a+pa,m-pa,b,n,k-pa); else if(a[pa⑴]>b[pb⑴]) return find_kth(a,m,b+pb,n-pb,k-pb); else return a[pa⑴]; } class Solution { public: double findMedianSortedArrays(int A[], int m, int B[], int n) { int sum=m+n; if(sum%2){ return find_kth(A,m,B,n,sum/2+1); } else return (find_kth(A,m,B,n,sum/2)+find_kth(A,m,B,n,sum/2+1))/2; } };

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 从Android Handler内部类到WeakReference的知识关联

下一篇 oracle从备份集中恢复归档日志方法

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点