要求：Median of Two Sorted Arrays (求两个排序数组的中位数)
分析：1. 两个数组含有的数字总数为偶数或奇数两种情况。2. 有数组可能为空。
解决方法：
1.排序法
时间复杂度O（m+n），空间复杂度 O(m+n)
归并排序到一个新的数组，求出中位数。
代码：
class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
int *C = new int[m+n];
int id1, id2, id3;
id1 = id2 = id3 = 0;
while(id1 < m && id2 < n) {
while(id1 < m && id2 < n && A[id1] <= B[id2]) C[id3++] = A[id1++];
while(id1 < m && id2 < n && B[id2] <= A[id1]) C[id3++] = B[id2++];
}
while(id1 < m) C[id3++] = A[id1++];
while(id2 < n) C[id3++] = B[id2++];
if(id3 & 0x1) {
id1 = C[id3>>1];
delete[] C;
return (double)id1;
}
else {
id1 = C[id3>>1];
id2 = C[(id3>>1)-1];
delete[] C;
return ((double)id1 + (double)id2) / 2.0;
}
}
};
2.使用两个指针查找
时间复杂度O((m+n)/2)，空间复杂度O(1)
数组 A ，B 分别使用一个指针，都从头或者从尾部开始走 (m+n) /2（m+n & 0x ==1 时） 步，找出中位数。
代码如下：
class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
if(m == ) return findMediaArray(B, n);
if(n == ) return findMediaArray(A, m);
unsigned id1, id2;
id1 = id2 = ;
if((m + n) & 0x1)
{
unsigned med = ;
while(id1 < m && id2 < n)
{
while(id1 < m && id2 < n && A[id1] <= B[id2])
{
++id1;
++med;
if(med == (m + n + ) >> ) return (double)A[id1 - ];
}
while(id1 < m && id2 < n && B[id2] <= A[id1])
{
++id2;
++med;
if(med == (m + n + ) >> ) return (double)B[id2 - ];
}
}
while(id2 < n)
{
++med;
if(med == (m + n + ) >> ) return (double)B[id2];
++id2;
}
while(id1 < m)
{
++med;
if(med == (m + n + ) >> ) return (double)A[id1];
++id1;
}
}
else
{
unsigned cnt = ;
int med1 = , med2 = ;
while(id1 < m && id2 < n)
{
while(id1 < m && id2 < n && A[id1] <= B[id2])
{
++id1;
++cnt;
if(cnt == (m + n) >> ) med1 = A[id1 - ];
if(cnt == ((m + n) >> ) + )
{
med2 = A[id1 - ];
return ((double)med1 +(double)med2) / ;
}
}
while(id1 < m && id2 < n && B[id2] <= A[id1])
{
++id2;
++cnt;
if(cnt == ((m + n) >> )) med1 = B[id2 - ];
if(cnt == ((m + n) >> ) + )
{
med2 = B[id2 - ];
return ((double)med1 +(double)med2) / ;
}
}
}
while(id2 < n)
{
++cnt;
if(cnt == (m + n) >> ) med1 = B[id2];
if(cnt == ((m + n) >> ) + )
{
med2 = B[id2];
return ((double)med1 +(double)med2) / ;
}
++id2;
}
while(id1 < m)
{
++cnt;
if(cnt == (m + n) >> ) med1 = A[id1];
if(cnt == ((m + n) >> ) + )
{
med2 = A[id1];
return ((double)med1 +(double)med2) / ;
}
++id1;
}
}
}
double findMediaArray(int A[], int m){
if(m == ) return 0.0;
if(m & 0x1) return (double)A[(m - ) >> ];
else return ((double)A[m >> ] + (double)A[(m >> ) - ]) / ;
}
};
code
3.类二分查找
时间复杂度O(lg((m+n)/2)) ~ O(lg(m+n))，空间复杂度O(1)
将问题化解为：查找两个数组中从小到大第 K 个元素。（从大到小亦可）以下为求解过程：
步骤：假定数组 A 中元素个数 m 小于数组 B 中元素个数 n 。从数组A中取出第 min(K/2，m)=pa 个元素，从数组B中取出第 K-pa = pb 个元素，若：
a. A[pa] < B[pb]，则将问题化为取数组 A+pa，与数组 B 中第 K - pb 个元素。
b. A[pa] = B[pb], 则第 k 个元素就是 A[pa] 或者 B[pb]。
c. A[pa] > B[pb]，则将问题化为取数组 A，与数组 B+pb 中第 K - pa 个元素。
代码：
double findKth(int A[], int m, int B[], int n, int k){
if(m > n) return findKth(B, n, A, m, k);
if(m == 0) return B[k-1];
if(k == 1) return min(A[0], B[0]);
int pa = min(k / 2, m), pb = k - pa;
if(A[pa - 1] < B[pb - 1]){
return findKth(A + pa, m - pa, B, n, k - pa);
}else if(A[pa - 1] > B[pb - 1]){
return findKth(A, m, B + pb, n - pb, k - pb);
}else{
return A[pa - 1];
}
}
class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
int total = m + n;
if(total == 0) return 0.0;
if(total & 0x1){
return findKth(A, m, B, n, (total + 1) >> 1);
}else{
return (findKth(A, m, B, n, total >> 1) + findKth(A, m, B, n, (total >> 1) + 1)) / 2.0;
}
}
};