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)).
Example 1:
nums1 = [1, 3] nums2 = [2] The median is 2.0
Example 2:
nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5
题意：
两个已排好序的数组，找出中位数，长度为奇数则是中间那个数，偶数则是中间两个数的平均值，复杂度要求O(log (m+n))。
思路：
可以转换为求在两个已排好序的数组中找第k个数。
设数列A元素个数为n，数列B元素个数为m，各自升序排序，求第k小元素
取A[k / 2] B[k / 2] 比较，如果 A[k / 2] > B[k / 2] 那么，所求的元素必然不在B的前k / 2个元素中，因为a中比B[k / 2]小的少于k/2个。 于是可以将A或B数列的前k/2元素删去，求剩下两个数列的k-k/2小元素，于是得到了数据规模变小的同类问题，递归解决。 如果 k / 2 大于某数列个数，所求元素必然不在另一数列的前k / 2个元素中，同上操作就好。
代码：
public class Solution { public int findkth(int[] nums1,int []nums2,int pos1,int pos2,int k){ // if(pos1==0&&pos2==0) System.out.println("---begin---"); System.out.println("pos1:"+pos1+" pos2:"+pos2+" k:"+k); if(pos1>=nums1.length) return nums2[pos2+k-1]; if(pos2>=nums2.length) return nums1[pos1+k-1]; if(k==1){ if(nums1[pos1]<=nums2[pos2]) return nums1[pos1]; return nums2[pos2]; } int index1=pos1+(k>>1)-1,index2=pos2+(k>>1)-1; // System.out.println("index1:"+index1+" index2:"+index2); int val1=((index1>=nums1.length)?Integer.MAX_VALUE:nums1[index1]); int val2=(index2>=nums2.length)?Integer.MAX_VALUE:nums2[index2]; if(val1>=val2){ return findkth(nums1,nums2,pos1,pos2+(k>>1),k-(k>>1)); } else{ return findkth(nums1,nums2,pos1+(k>>1),pos2,k-(k>>1)); } } public double findMedianSortedArrays(int[] nums1, int[] nums2) { if(nums1.length+nums2.length==0) return 0; int k=(nums1.length+nums2.length+1)>>1; if(((nums1.length+nums2.length)&1)==1){ return findkth(nums1,nums2,0,0,k); } return (findkth(nums1,nums2,0,0,k)+findkth(nums1,nums2,0,0,k+1))/2.0; } }
另外，如果 k / 2 大于某数列个数，设该数列还有num未比较，可以比较该数列最后一个与另外一个数列的第k-num个数，同样的道理谁大删除另外一边。这里要注意的是，第二个数组可能没有足够的个数，需要每次保证先分配小的。如数据
2 3 4 5 6 1 找第4个数，如果第一个数组分配2个，第2个数组则没有2个可以分配
这种方法会稍快一些，这题时间卡的严格，k/2可以写成k>>1来优化
代码：
public class Solution { public int findkth_pre(int[] nums1,int []nums2,int pos1,int pos2,int k){ if(pos1==nums1.length) return nums2[pos2+k-1]; if(pos2==nums2.length) return nums1[pos1+k-1]; if(k==1){ if(nums1[pos1]<=nums2[pos2]) return nums1[pos1]; return nums2[pos2]; } int index1,index2; //保证小的分配不超过长度 谁小先分配谁 if(nums1.length-pos1<nums2.length-pos2){ index1=pos1+(k>>1)-1; if(index1>=nums1.length) index1=nums1.length-1; index2=pos2+k-(index1-pos1+1)-1; } else{ index2=pos2+(k>>1)-1; if(index2>=nums2.length) index2=nums2.length-1; index1=pos1+k-(index2-pos2+1)-1; } if(nums1[index1]>nums2[index2]){ return findkth_pre(nums1,nums2,pos1,index2+1,k-(index2-pos2+1)); } else{ return findkth_pre(nums1,nums2,index1+1,pos2,k-(index1-pos1+1)); } } public double findMedianSortedArrays(int[] nums1, int[] nums2) { if(nums1.length+nums2.length==0) return 0; int k=(nums1.length+nums2.length+1)>>1; if(((nums1.length+nums2.length)&1)==1){ return findkth_pre(nums1,nums2,0,0,k); } return (findkth_pre(nums1,nums2,0,0,k)+findkth_pre(nums1,nums2,0,0,k+1))/2.0; } }
