首页 > 代码库 > [Leetcode] Median of Two Sorted Arrays
[Leetcode] Median of Two Sorted Arrays
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)).
Solution:
public class Solution { public double findMedianSortedArrays(int A[], int B[]) { int m=A.length; int n=B.length; int total=m+n; if(total%2!=0){ return findKthNumber(A,m,B,n,total/2+1); }else{ return (findKthNumber(A,m,B,n,total/2)+findKthNumber(A,m,B,n,total/2+1))/2; } } private double findKthNumber(int[] a, int m, int[] b, int n, int k) { // TODO Auto-generated method stub if(m>n) return findKthNumber(b, n, a, m, k); if(m==0) return b[k-1]; if(k==1) return Math.min(a[0], b[0]); int pa=Math.min(k/2, m); int pb=k-pa; if(a[pa-1]<b[pb-1]){ int[] c=Arrays.copyOfRange(a, pa, m); return findKthNumber(c, m-pa, b,n, k-pa); }else if(a[pa-1]>b[pb-1]){ int[] d=Arrays.copyOfRange(b, pb, n); return findKthNumber(a, m, d, n-pb, k-pb); }else{ return a[pa-1]; } }}
此题甚难啊觉得。。。
可以参考一下大神的图，再自己看看代码改改图就可以理解啦：
http://www.narutoacm.com/archives/median-of-two-sorted-arrays/
[Leetcode] Median of Two Sorted Arrays
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。