在LeetCode上看到的一道题目：
给定两个数组大小分别为m和n，排好了序，可能是降序也可能是升序，求两个数组所有数字的中位数，要求算法复杂度为O(m+n)。这里的中位数是如下定义的：如果总个数为偶数那么就取第n/2和n/2+1个数的平均数，例如：
两个数组分别为：[1,2] 和[1,2]那么中位数就应该是1,1,2,2的中位数，也就是：1.5
对于这个题目，最简单的做法自然是将两个数组在O(m+n)时间内分别整理成升序排列，然后合并两个数组到一个大的数组C里面，最后直接求C的中位数即可，这个做法的代码我就不写出来了，还是比较容易写的，但是最大的缺点在于：浪费空间，数组C的使用就导致内存多了m+n的开销。
我的做法是类似于合并数组A和B的思路，但是空间开销要少很多。
首先处理m为0，或者n为0的情况。然后用medianIndex记录比中位数小的数的个数+1。
紧接着处理A和B的降序或者升序问题。
然后依次从最小的数开始计数（使用count记录），直到找到medianIndex个数为止。
backwardOne和backwardTwo用来记录目前为止所找到的最大数和倒数第二大的数，这在m+n为偶数时要用到。
double findMedianSortedArrays(int A[], int m, int B[], int n)
{
if(m==0&&n!=0)
{
return n%2 == 1?B[(n+1)/2-1]:(B[n/2]+B[n/2-1])/2.0;
}
if(n==0&&m!=0)
{
return m%2 == 1?A[(m+1)/2-1]:(A[m/2]+A[m/2-1])/2.0;
}
double result = 0.0;
int medianIndex = 0;
if((m+n)%2 == 0)
{
medianIndex = (m+n)/2 +1;
}
else
{
medianIndex = (m+n+1)/2;
}
int addA = 1,addB=1;
int startA = 0 ,endA = m;
int startB = 0 ,endB = n;
if(m > 1 && n>1)
{
if(A[0] > A[1])
{
addA = -1;
startA = m-1;
endA = 0;
}
if(B[0] > B[1])
{
addB = -1;
startB = n-1;
endB = 0;
}
}
int count=0;
int i=0,j=0;
int backwardOne = 0,backwardTwo = 0;
for(i=startA,j=startB;i!=endA&&j!=endB;)
{
if(A[i]<B[j])
{
backwardTwo = backwardOne;
backwardOne = A[i];
i+=addA;
count++;
if(count == medianIndex)
{
return (m+n)%2==1?backwardOne:(backwardOne+backwardTwo)/2.0;
}
}
else
{
backwardTwo = backwardOne;
backwardOne = B[j];
j+=addB;
count++;
if(count == medianIndex)
{
return (m+n)%2==1?backwardOne:(backwardOne+backwardTwo)/2.0;
}
}
}
if(count < medianIndex)
{
if(i==endA)
{
if(addB == 1)
{
if(medianIndex - count >= 2)
{
backwardOne = B[medianIndex - m -2];
}
return (m+n)%2==1?B[medianIndex - m -1]:(B[medianIndex - m -1]+backwardOne)/2.0;
}
else
{
if(medianIndex - count >= 2)
{
backwardOne = B[medianIndex - m];
}
return (m+n)%2==1?B[n-(medianIndex - m - 1)]:(B[n-(medianIndex - m - 1)]+backwardOne)/2.0;
}
}
else
{
if(addA == 1)
{
if(medianIndex - count >= 2)
{
backwardOne = A[medianIndex - n -2];
}
return (m+n)%2==1?A[medianIndex - n -1]:(A[medianIndex - n -1]+backwardOne)/2.0;
}
else
{
if(medianIndex - count >= 2)
{
backwardOne = A[medianIndex - m];
}
return (m+n)%2==1?A[m-(medianIndex - n - 1)]:(A[m-(medianIndex - n - 1)]+backwardOne)/2.0;
}
}
}
}