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)).
For example, supposing the total length of two arrays is N. If N is an odd number, we need to find the N / 2 + 1 th number in two arrays, otherwise we need to find N / 2 th and N / 2 + 1 th number and return the average ofthem.
第二遍做的思路,参考了code Ganker的想法,问题等价于求两个array的第k个(这道题k = (m + n) / 2, 假设m和n分别是两个数组的元素个数,且从第1大的数开始)大的数是多少。基本思路是每次通过查看两个数组的第k/2大的数(是A[k/2-1],B[k/2-1]),如果A[k/2-1]=B[k/2-1],说明当前这个数即为两个数组剩余元素的第k大的数,如果A[k/2-1]>B[k/2-1], 那么说明B的前k/2个元素都不是我们要的第k大的数(原因:反证法,如果B的第k/2大的数是两个数组第k大的数,那么这k个数,B已经提供了k/2个,所以A也要提供k/2个,那么A[k/2-1]也在被提供之列。但A[k/2-1]>B[k/2-1], 所以A[k/2-1]才是两个数组第k大的数,与之前假设B[k/2-1]是第k大的数矛盾),反之则排除A的前k/2个,如此每次可以排除k/2个元素,最终k=1、或者m或者n小的那个变成0时,即达到base case。总的时间复杂度为O(logk),空间复杂度也是O(logk),即为递归栈大小。在这个题目中因为k=(m+n)/2,所以复杂度是O(log(m+n))。
1 public class Solution { 2 public double findMedianSortedArrays(int A[], int B[]) { 3 if((A.length+B.length)%2==1) 4 return helper(A,B,0,A.length-1,0,B.length-1,(A.length+B.length)/2+1); 5 else 6 return (helper(A,B,0,A.length-1,0,B.length-1,(A.length+B.length)/2) 7 +helper(A,B,0,A.length-1,0,B.length-1,(A.length+B.length)/2+1))/2.0; 8 } 9 10 PRivate int helper(int A[], int B[], int i, int i2, int j, int j2, int k)11 {12 int m = i2-i+1;13 int n = j2-j+1;14 if(m>n)15 return helper(B,A,j,j2,i,i2,k);16 if(m==0)17 return B[j+k-1];18 if(k==1)19 return Math.min(A[i],B[j]);20 int posA = Math.min(k/2,m);21 int posB = k-posA;22 if(A[i+posA-1]==B[j+posB-1])23 return A[i+posA-1];24 else if(A[i+posA-1]<B[j+posB-1])25 return helper(A,B,i+posA,i2,j,j2,k-posA);26 else27 return helper(A,B,i,i2,j+posB,j2,k-posB);28 }29 }
看以下这个别人的解法也许更好懂一点:
在计算中位数Median时候,需要根据奇偶分类讨论。
解决此题的方法可以依照:寻找一个unioned sorted array中的第k大(从1开始数)的数。因而等价于寻找并判断两个sorted array中第k/2(从1开始数)大的数。
特殊化到求median,那么对于奇数来说,就是求第(m+n)/2+1(从1开始数)大的数。
而对于偶数来说,就是求第(m+n)/2大(从1开始数)和第(m+n)/2+1大(从1开始数)的数的算术平均值。
那么如何判断两个有序数组A,B中第k大的数呢?
我们需要判断A[k/2-1]和B[k/2-1]的大小。
如果A[k/2-1]==B[k/2-1],那么这个数就是两个数组中第k大的数。
如果A[k/2-1]<B[k/2-1], 那么说明A[0]到A[k/2-1]都不可能是第k大的数,所以需要舍弃这一半,继续从A[k/2]到A[A.length-1]继续找。当然,因为这里舍弃了A[0]到A[k/2-1]这k/2个数,那么第k大也就变成了,第k-k/2个大的数了。
如果 A[k/2-1]>B[k/2-1],就做之前对称的操作就好。
这样整个问题就迎刃而解了。
当然,边界条件页不能少,需要判断是否有一个数组长度为0,以及k==1时候的情况。
因为除法是向下取整,并且页为了方便起见,对每个数组的分半操作采取:
int partA = Math.min(k/2,m);int partB = k - partA;
为了能保证上面的分半操作正确,需要保证A数组的长度小于B数组的长度。
同时,在返回结果时候,注意精度问题,返回double型的就好。
1 public class Solution { 2 public double findMedianSortedArrays(int A[], int B[]) { 3 int m = A.length; 4 int n = B.length; 5 int total = (m+n); 6 if(total%2 == 0){ 7 double x = findKth(A,0,m-1,B,0,n-1,total/2); 8 double y = findKth(A,0,m-1,B,0,n-1,total/2+1); 9 return (x+y)/2.0; 10 }else{ 11 return findKth(A,0,m-1,B,0,n-1,total/2+1); 12 } 13 } 14 15 public double findKth(int[] A, int astart, int aend, int[] B, int bstart, int bend, int k){ 16 int m = aend-astart+1; 17 int n = bend-bstart+1; 18 19 if(m>n){ 20 return findKth(B,bstart,bend,A,astart,aend,k); 21 } 22 23 if(m == 0 ){ 24 return B[bstart+k-1]; //这里B[k-1]也是对的,不懂?估计跟B的长度总是调成最长的那个有关25 } 26 27 if(k==1){ 28 return Math.min(A[astart],B[bstart]); 29 } 30 31 int partA = Math.min(m,k/2); 32 int partB = k-partA; 33 if(A[astart+partA-1]<B[bstart+partB-1]){ 34 return findKth(A,astart+partA, aend, B, bstart, bend, k-partA); 35 }else if(A[astart+partA-1]>B[bstart+partB-1]){ 36 return findKth(A,astart, aend, B, bstart+partB, bend, k-partB); 37 }else{ 38 return A[astart+partA-1]; 39 } 40 41 } 42 }
新闻热点
疑难解答