Median of Two Sorted Arrays

1. Question

找两个有序数组的中位数。时间复杂度O(log(m+n))

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)).

2. Solution

2.1 O(nlogn)

将两个数组拷到新数组中，对新数组排序

 1 public class Solution {
 2     public double findMedianSortedArrays( int[] a, int[] b ){
 3         int[] c = new int[a.length + b.length];
 4         System.arraycopy(a, 0, c, 0, a.length);
 5         System.arraycopy(b, 0, c, a.length, b.length);
 6         Arrays.sort(c);
 7         int mid = c.length / 2;
 8         if( c.length % 2 == 0 )
 9             return ( c[mid-1] + c[mid] ) / 2.0;
10         return c[mid];
11     }
12 }

sort

2.2 O(n/2)---->O(n)

将两个数组合并。

 1 public class Solution {
 2     public double findMedianSortedArrays( int[] a, int[] b ){
 3         int len1 = a.length;
 4         int len2 = b.length;
 5         int len = (len1 + len2) / 2 + 1;
 6         int[] c = new int[len];
 7         int ia;
 8         int ib;
 9         int ic;
10         for( ia=0, ib=0, ic=0; ia<len1 && ib<len2 && ic<len; ic++ ){
11             if( a[ia] <= b[ib] )
12                 c[ic] = a[ia++];
13             else
14                 c[ic] = b[ib++];
15         }
16         for( ; ia<len1 && ic<len; ic++, ia++ )
17             c[ic] = a[ia];
18         for( ; ib<len2 && ic<len; ic++, ib++ )
19             c[ic] = b[ib];    
20         ic--;
21         if( (len1 + len2) % 2 == 0 )
22             return ( c[ic] + c[ic-1] ) / 2.0;
23         return c[ic];
24     }
25 }

merge

2.3 O(logn)

定义如下变量：

m1：nums1的中位数（有m/2个数小于等于m1）
m2：nums2的中位数（有n/2个数小于等于m2）

判断m1和m2的大小，以舍弃一半的数组：

m1<m2：有(m+n)/2个数<=m2，即m1必然存在于合并后数组的前半部分，m2存在于后半部分。则中位数存在于nums1的后半部分或nums2的前半部分；
m1>m2：同上，中位数存在于nums1的前半部分或nums2的后半部分；
m1 == m2：m1即是中位数

 1 public class Solution {
 2     // find the kth big number;
 3     public int findKth( int[] a,  int afrom, int ato, int[] b, int bfrom, int bto, int k ){
 4         //we assume that m<=n
 5         int m = ato - afrom + 1;
 6         int n = bto - bfrom + 1;
 7         if( m > n )
 8             return findKth( b, bfrom, bto, a, afrom, ato, k);
 9         if( m == 0  )
10             return b[k-1];
11         if( k==1 )
12             return ( a[afrom] < b[bfrom] ) ? a[afrom] : b[bfrom];
13         int na = ( k/2 < m )? k/2 : m;
14         int nb = k-na;
15         int pa = na + afrom -1;
16         int pb = nb + bfrom -1;
17         if( a[pa] > b[pb] )
18             return findKth( a, afrom, pa, b, pb+1, bto, k-nb );
19         if( a[pa] < b[pb] )
20             return findKth( a, pa+1, ato, b, bfrom, pb, k-na );
21         return b[pb];
22     }
23     
24     //O( log(m+n) ) time
25     public double findMedianSortedArrays( int[] a, int[] b ){
26         int len = a.length + b.length;
27         if( len % 2 == 0 )
28             return ( findKth( a, 0, a.length-1, b, 0, b.length-1,  len/2 ) + findKth( a, 0, a.length-1,  b, 0, b.length-1,  len/2+1 ) ) / 2.0;
29         else 
30             return findKth( a, 0, a.length-1, b, 0, b.length-1,  len/2+1 );
31     }
32 }

binary