首页 > 代码库 > 【算法导论学习-016】两个已排过序的等长数组的中位数(median of two sorted arrays)
【算法导论学习-016】两个已排过序的等长数组的中位数(median of two sorted arrays)
问题来源
《算法导论》P223 9.3-8:
Let X[1..n] and Y[1..n] be two arrays, each containing nnumbers already in sorted order. Give an O(lgn)-time algorithm to find themedian of all 2n elements in arrays X and Y.
翻译过来即:求两个等长(n个元素)的已排序数组A和B的中位数
方案1:对两个数组进行归并直到统计到第n个元素(复杂度O(n))
方案2:从A的中位数出发,二分查找直到满足条件(复杂度O(lgn))
参考:https://gist.github.com/richzw/3780428。注意:参考代码中有明显错误。
这也是题目中的要求。从A的中位数出发,即k=(n-1)/2,则B对应的指针是n-1-k的话能保证A中小于A[k]的元素个数为k个,B中小于B[n-1-k]-的元素为为n-1-k个,只要二分查找到满足下面条件的A[k]就行——A和B中小于A[k]的元素个数为n-1个,A[k]为第n个数,即中位数。
A[k]>=B[n-k-1]&&A[k]<=B[n-k]
/** * 创建时间:2014年8月18日上午10:25:49 * 项目名称:Test * @author CaoYanfeng * @sinceJDK 1.6.0_21 * 类说明: 编译通过 */ public classMedianofTowArray { /** * @paramargs */ public static voidmain(String[] args) { // TODOAuto-generated method stub int[] array1={4,5,6,7}; int[] array2={3,5,6,7}; /*返回{3,4,5,5,6,6,7,7}的中间值,即6或者5*/ int result1=MedianofTowArray2(array1, array2); int result2=getMedian(array1, 0, array1.length-1, array1.length, array2); System.out.println("进行初始判断后再递归:"+result1+"\n直接递归:"+result2); } /*排除两种特殊情况(即A与B不重合的情况)再进行递归进行二分查找*/ public static int MedianofTowArray2(int[] array1,int[] array2) { int n=array1.length; if (array1[n-1]<array2[0]){ return array1[n-1]; }else if (array2[n-1]<array1[0]){ return array2[n-1]; }else { return getMedian(array1, 0, n-1, n, array2); } } /*直接递归进行二分查找,参考代码中有错误,这里已经修改*/ public static intgetMedian(int[] array1,int low,int high,int n,int[] array2) { int k=(high+low)/2; if (k==n-1||k==0){ return array1[k]; }else if (k>0&&k<n-1&&array1[k]>=array2[n-k-1]&&array1[k]<=array2[n-k]) { return array1[k]; }else if (array1[k]>array2[n-k-1]){ return getMedian(array1, low, k-1, n, array2); }else { return getMedian(array1, k+1, high, n, array2); } } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。