题目意思很简单将两个有序数组合并之后的中位数找出来。题目要求使用log(m+n)的时间复杂度来做。

虽然言简意赅，但不得不承认这个题目我自己想了好久也没做出来，隐约觉得应该使用寻找第k大数的算法来做，但是具体到这个题目，编码多次都以失败告终，所以不得不去网上参考下别人的思路和代码。

参考链接：http://blog.csdn.net/zxzxy1988/article/details/8587244

但是这个方法现在已经无法在leetcode上AC，需要在两个递归的return处进行修改。

思路是这样的：

我们寻找两个数组的第k个数，那么我们首先找到两个数组中的第(k/2-1)个数。比较两个数组中这个数的大小来进行不同递归。

 

代码如下：

1     int min(int a,int b) 2     { 3         return a>b?b:a; 4     } 5     double findknumber(int *a,int *b,int al,int bl,int k) 6     { 7         if (al > bl) 8             return findknumber(b, a, bl, al, k); 9         if (al == 0)10             return b[k - 1];11         if (k == 1)12             return min(a[0], b[0]);13         int aindex = min(k / 2, al);14         int bindex = k - aindex;15         if (a[aindex - 1] < b[bindex - 1])16             return findknumber(a + aindex, b, al - aindex, bindex, k - aindex);17         else if (a[aindex - 1] > b[bindex - 1])18             return findknumber(a, b + bindex, aindex, bl - bindex, k - bindex);19         else20             return a[aindex - 1];21 22 23     }24     double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {25         int total=nums1Size+nums2Size;26         if(total%2==1)27             return findknumber(nums1,nums2,nums1Size,nums2Size,total/2+1);28         else29             return (findknumber(nums1,nums2,nums1Size,nums2Size,total/2+1)30                     +findknumber(nums1,nums2,nums1Size,nums2Size,total/2))/2.0;31 32     }

这个代码还存在两个问题，后续我再补充：

存在一个找第k个数的坐标问题；

这个算法的真实时间复杂度如何；