首页 > 代码库 > Median of Two Sorted Arrays
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)).
从两个有序的数组中找到中位数，然后。。。然后这个题目真心变态！
方法一：归并排序，时间复杂度直接O(m+n)，可以改进，找到第(m+n)/2个数，直接输出答案
方法二：设数组长度为n，元素为a0,a1,a2,a3,.....,an-1，那么
如果 n 是奇数，那么数组的中位数为 a[(n-1)/2]，即上中位数和下中位数是同一个数
如果 n 是偶数，那么数组的上中位数为 a[(n-1)/2]，下中位数为 a[n/2]
注：该题所求中位数是 (上中位数+下中位数)/2
因此需要分别求出两数组合并后的上中位数和下中位数。求上中位数的步骤如下：
1. 先保证A数组长度小于B数组，便于后面逻辑处理
2. 当A数组长度为0时，可以直接通过B数组求出上中位数
当A数组长度为1时，这时B分3种情况，同时假设B的上中位数为B[bmid]
a. B长度为1，那么上中位数就是他们之间的最小值
b. B长度为奇数，那么需要比较A中仅有的元素与B[bmid]、B[bmid-1]想比较，进而得出两数组的中位数
c. B长度为偶数，同样需要比较A中仅有的元素与B[bmid]、B[bmid+1]想比较，进而得出两数组的中位数
当A数组长度大于1时，这是B数组长度大于等于A数组长度，此时我们可以直接得出A数组的上中位数A[amid]，B数组的上中位数B[bmid]
如果A[amid] = B[bmid]，那么两数组的上中位数就是A[amid]
如果A[amid] < B[bmid]，那么说明两数组上中位数在A[amid]后面，B[bmid]前面，故可以同时裁剪 A数组中[0...m/2-1]元素及B[n-m/2....n-1]
接着在A[m/2....m-1]和B[0.....n-m/2-1]继续找上中位数
如果A[amid] > B[bmid]，那么说明两数组的中位数在A[amid]前面，B[bmid]后面，故同样裁剪A后面m/2个元素，B前面m/2个元素
接着在A[0.....m-m/2-1]和B[m/2....n-1]中继续找上中位数
注：在数组中有一半的元素不超过中位数，有一半的元素不小于中位数，故 同时去除k个比中位数小的数，k个比中位数大的数，那么得到的子数组的中位数和原数组的中位数是相同的。
求下中位数的方法与上类似，代码如下：
1 class Solution { 2 public: 3 double findMedianSortedArrays(int A[], int m, int B[], int n) { 4 return ( 1.0*findUpMedian(A,m,B,n) + findDownMedian(A,m,B,n) ) / 2; //求上中位数和下中位数取均值 5 } 6 7 double findUpMedian(int A[], int m, int B[], int n) { //求上中位数 8 if( m > n ) { //保证m<=n 9 swap( A, B );10 swap( m, n );11 }12 int amid = (m-1)/2, bmid = (n-1)/2; //直接定位两数组的上中位数13 if( m == 0 ) return B[bmid];14 if( m == 1 ) {15 if( n == 1 ) return min(A[amid], B[bmid]);16 else if( n & 1 ) { //奇数17 if( A[amid] < B[bmid-1] ) return B[bmid-1];18 else if( A[amid] < B[bmid] ) return A[amid];19 else return B[bmid];20 }21 else { //偶数22 if( A[amid] < B[bmid] ) return B[bmid];23 else if( A[amid] < B[bmid+1] ) return A[amid];24 else return B[bmid+1];25 }26 }27 else {28 if( A[amid] == B[bmid] ) return A[amid];29 int ncuts = m/2; //每次切割都是切最小数组长度的一半30 if( A[amid] < B[bmid] ) return findUpMedian(A+ncuts, m-ncuts, B, n-ncuts);31 else return findUpMedian(A, m-ncuts, B+ncuts, n-ncuts);32 }33 }34 35 double findDownMedian(int A[], int m, int B[], int n) { //求下中位数36 if( m > n ) {37 swap( A, B );38 swap( m, n );39 }40 int amid = m/2, bmid = n/2; //直接定位下中位数41 if( m == 0 ) return B[bmid];42 if( m == 1 ) {43 if( n == 1 ) return max(A[amid], B[bmid]);44 else if( n & 1 ) { //奇数45 if( A[amid] > B[bmid+1] ) return B[bmid+1];46 else if( A[amid] > B[bmid] ) return A[amid];47 else return B[bmid];48 }49 else { //偶数50 if( A[amid] < B[bmid-1] ) return B[bmid-1];51 else if( A[amid] < B[bmid] ) return A[amid];52 else return B[bmid];53 }54 }55 else {56 if( A[amid] == B[bmid] ) return A[amid];57 int ncuts = m/2; //每次切割都是切最小数组长度的一半58 if( A[amid] < B[bmid] ) return findDownMedian(A+ncuts, m-ncuts, B, n-ncuts);59 else return findDownMedian(A, m-ncuts, B+ncuts, n-ncuts);60 }61 }62 };
方法三：转化为在两个有序数组中求第k个数最小数，步骤如下：
1. 如果a或b为空，那么直接求出第k小
2. 假设元素"平均分配"的情况下，如果第k小的数在a数组，设下标为i = m/(m+n)*(k-1)，如果第k小的数在b数组，那么有 i+1 + j+1 = k，则 j = k - i - 2;
即保证了 保证a[i]及其前面的元素个数+b[j]及其前面的元素个数=k
此时，如果a[i] == b[j] 那说明第k-1及k的元素都为a[i]
若a[i] < b[j]，那第k个数在a[i]后面，b[j]前面，就可以裁剪掉a数组前i+1个元素，在a[i+1....m]，b[0....j]中找
若a[i] > b[j]，那第k个数在b[j]后面，a[i]前面，就可以裁减掉b数组前j+1个元素，在b[j+1....n]，a[0...i]中找
当k = 1或a[i] = b[i]的时候收敛，代码如下：
1 class Solution { 2 public: 3 double findMedianSortedArrays(int A[], int m, int B[], int n) { 4 if( (m+n) & 1 ) //元素个数为奇数的情况 5 return findKthSmallest(A, m, B, n, (m+n+1)/2); 6 else //元素个数为偶数的情况 7 return 1.0*(findKthSmallest(A, m, B, n, (m+n)/2)+findKthSmallest(A, m, B, n, (m+n)/2+1))/2; 8 } 9 10 int findKthSmallest(int* a, int m, int* b, int n, int k) {11 if( m == 0 ) return b[k-1];12 if( n == 0 ) return a[k-1];13 if( k == 1 ) return min(a[0], b[0]); //收敛的条件14 int i = 1.0*m/(m+n) * (k-1); //在A数组大致预测i15 int j = k-i-2; //保证a[i]及其前面的元素个数+b[j]及其前面的元素个数=k，即i+1 + j+1 = k16 if( a[i] == b[j] ) return a[i]; //如果相等，说明第k-1及k的元素都为a[i]17 if( a[i] < b[j] ) return findKthSmallest(a+i+1, m-i-1, b, j+1, k-i-1); //说明在a[i]后面，b[j]前面，故可裁剪a中前i+1个数18 else return findKthSmallest(a, i+1, b+j+1, n-j-1, k-j-1); //说明在b[j]后面，a[i]前面，故可裁剪b中前j+1个数19 }20 };
Median of Two Sorted Arrays