Description
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)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
分析
给定两个以排序的数组，要求输出这两个数组组成的新数组的中位数。
如[1,2]和[3],其中位数为2.[1,2]和[3,4]中位数为(2+3)/2。题目的难点在于要求复杂度不大于O(log (m+n))。
中位数：中位数是指一个可以将一系列数字串分为长度相等，并且中位数左边的数均不大于右边的数。
根据中位数的这个性质，我们只要找到一个数，使得两边的数子个数相同，并且左边的不大于右边的数，即可完成任务。
思路
由于给定的两个数组元素相对大小并不确定，因此数组元素直接拼接成一个数组并不实际。
我们可以将这两个数组分别划分，将其分成左右两部分，两个数组左边的部分构成一个新数组，右边的构成一个新数组。若左边的元素个数正好等于右边的元素个数，并且左边的最大数小于等于右边的最小数。这样我们就找到了中位数。
设较长的数组为pt1,长度为n,较短的数组为pt2，长度为m，两个整数i，j将这两个数组分为两部分。
设pt1分割后左边最大值为l1，右边最小值为r1，pt2分割后左边最大值为l2，右边最小值为r2。
若l1<=r2 && l2<=r1,则此时满足中位的条件。
中位数等于 [max(l1,l2)+min(r1,r2)]/2。
若l1>r2,则需要减小l1的值，即减小i的值。
若l2>r1,则需要减少l2的值，因为i+j保持不变，j减小，i必定增加。
i与j的几种边界条件：
- i==0，此时短数组整体大于长数组，中位数位于长数组中，且i与j可能是正好需要的分割，但l2不存在（越界），因此将l2赋为最小值，保证判断正确。
- j==0，此时长数组整体大于短数组，中位数位于长数组中，且i与j可能是所求分割。
- i==2*m，此时短数组整体小于长数组，中位数位于长数组中，i与j可能符合要求，将r2赋最大值保证判断正确。
- j=2*n，此时长数组整体小于短数组，中位数位于长数组中，i与j可能符合条件。
分割
对于数组进行分割，我们一般需要根据数组长度分奇数，偶数两种情况处理，比较麻烦。简单的方法是我们可以通过虚拟添加'#'符号的方式是得所有数组的长度均为奇数，便于处理。
有趣的是这样添加虚拟'#'符号以后，假设分割位置为i，则分割后
l=pt[(i-1)/2];
r=pt[i/2];
C语言代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size)
{
int n,m,i,j,imax,imin,temp,l1,l2,r1,r2;
n=nums1Size;
m=nums2Size; //较短数组
int *pt1,*pt2;
int maxleft,minright;
float med;
if(m>=n)
{
temp=n;
n=m;
m=temp;
pt1=nums2; //较长数组
pt2=nums1; //较短数组
}
else
{
pt1=nums1;
pt2=nums2;
}
imin=0;
imax=2*m; //虚拟添加'#'分割
while(imin<=imax)
{
i=imin+(imax-imin)/2;
j=m+n-i;
l1=(i==0)? INT_MIN : pt2[(i-1)/2]; //i==0,说明，短数组整体比长数组大，说明中位数在长数组中，此时，有可能i和j即为符合要求的分割，而此时l1不存在，因此给l1赋最小数，保证判断正确。下面赋最大值也是同样的考虑。
l2=(j==0)? INT_MIN : pt1[(j-1)/2]; //j==0,说明，长数组整体比短数组大，短数组整体比长数组小，i需要减小 ，j增加（i减小条件r2<l1）。
r1=(i==2*m)? INT_MAX : pt2[i/2]; //i==2*m，说明短数组整体比长数组小 ， i需要减小（i减小条件r2<l1）。
r2=(j==2*n)? INT_MAX : pt1[j/2]; //j==2*n,说明短数组整体比长数组大， i需要增加 (增加条件l2>r1)。
if(l1<=r2&&l2<=r1)
{
maxleft=(l1>l2)? l1:l2;
minright=(r1<r2)? r1:r2;
return ((double)maxleft+(double)minright)/2;
}
else if(r2<l1)
imax=i-1;
else
imin=i+1;
}
return -1;
}
int main()
{
int arr1[]={1,3,5,7,8,9};
int arr2[]={10,11,12,13};
int *p1,*p2;
p1=arr1;
p2=arr2;
int med=0;
med=findMedianSortedArrays(p1,6,p2,4);
return 0;
}
参考文献
[1] https://leetcode.com/problems/median-of-two-sorted-arrays/#/description
[2] https://discuss.leetcode.com/topic/16797/very-concise-o-log-min-m-n-iterative-solution-with-detailed-explanation
[3]https://hk029.gitbooks.io/leetbook/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/035.%20Search%20Insert%20Position[M],md
[4]http://blog.csdn.net/hk2291976/article/details/51107778
