There are two sorted arrays nums1 and nums2 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)).
参考别人的代码http://www.cnblogs.com/duanqiong/p/4415049.html
public class Solution { public static double findMedianSortedArrays(int[] nums1, int[] nums2) { int len1=nums1.length; int len2=nums2.length; int totalLength=len1+len2; int k=totalLength/2+1; if(totalLength%2==1){ //总长度为奇数 return findKth(nums1,0,len1,nums2,0,len2,k); } else{ //总长度为偶数 return (findKth(nums1,0,len1,nums2,0,len2,k-1)+findKth(nums1,0,len1,nums2,0,len2,k))/2; } } public static double findKth(int num1[],int begin1,int len1,int num2[],int begin2,int len2,int k){ if(len1>len2) return findKth(num2, begin2, len2, num1, begin1, len1, k); //确保len1<len2 if(len1==0) return num2[begin2+k-1]; if(k==1) return Math.min(num1[begin1], num2[begin2]); int tmp1=Math.min(k/2, len1); int tmp2=k-tmp1; if(num1[begin1+tmp1-1]<num2[begin2+tmp2-1]) return findKth(num1, begin1+tmp1, len1-tmp1, num2, begin2, len2, k-tmp1); else if(num1[begin1+tmp1-1]>num2[begin2+tmp2-1]) return findKth(num1, begin1, len1, num2, begin2+tmp2, len2-tmp2, k-tmp2); else return num1[begin1+tmp1-1]; } public static void main(String[] args) { int[] a={1}; int[] b={1}; double median=findMedianSortedArrays(a,b); System.out.println(median); } }
leetcode 004 Median of Two Sorted Arrays(java)
原文：http://www.cnblogs.com/WillsCheng/p/5043698.html