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)).
有两个有序的数组num1和num2,容量分别为m,n。找到两个数组的中位数。整个的时间复杂度应该为O(log(m+n)).
解：
求中位数，则应该分别考虑m+n的 奇偶性，然后调用一个函数，返回两个向量合并成一个有序序列，的第k个值。
接下来我们主要的任务就是写出这个函数。
我们不妨设n<=m,因为两个数组可以互换顺序，不影响结果。我们在num1数组中找到第p=min(k/2,n)个数a，在num2中找到第k-p的数b。相比较：如果a>b,那么我们可以确定我们最终要找的数载b之后，则我们重新确定num2数组（去掉包括b之前的元素），递归寻找第k-p个数，反之同理。这事我们再确定结束条件，当其中一个数组为空的时候，直接返回另一个数组第k个数。当k等于1的时候返回min(num1[0],num[0])。
代码如下(C++)：
class Solution { public: //寻找两个数组如果合并为一个有序数组之后的第k个数。 int ans(vector<int>& nums1,vector<int>& nums2,int k){ int n = nums1.size(); int m = nums2.size(); if(n > m){ return ans(nums2,nums1,k); } if(n == 0) return nums2[k-1]; if(k == 1) return min(nums1[0],nums2[0]); int pa = min(k/2,n),pb = k - pa; if(nums1[pa - 1] < nums2[pb - 1] ){ vector<int> a(nums1.begin() + pa, nums1.end()); return ans(a,nums2,k - pa); } else if(nums1[pa - 1] > nums2[pb - 1]){ vector<int> b(nums2.begin() + pb,nums2.end()); return ans(nums1,b,k - pb); } else return nums1[pa-1]; } double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int n = nums1.size(); int m = nums2.size(); int k = (n + m)/2; if((m + n)%2){ return ans(nums1,nums2,k + 1); } else { return (ans(nums1,nums2,k) + ans(nums1,nums2,k+1))/2.0; } }
时间复杂度因为通过递归，为O(log(m+n))。
空间复杂度为O(1)。
