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
思路：这题更通用的形式是，给定两个已经排序好的数组，找到两者所有元素中第k大的元素。 方法一：直接把两个数组装进一个数组后sort()排序,求第k个大的元素，时间复杂度是O((m+n)log(m+n))。 方法二：可以用一个计数器，记录当前已经找到第m大的元素。同时我们使用两个指针pA和pB,分别指向A和B数组的第一个元素，使用类似merge sort的原理，如果数组A当前元素小，那么pA++,同时m++；如果数组B当前元素小，那么pB++,同时m++。最终m等于k的时候，就得到了我们的答案，时间复杂度是O(k),当k很接近m+n的时候，这个方法时间复杂度还是0(m+n)。 方法三：由于A和B是有序的，我们应该充分利用这里面的信息，类似于二分查找，时间复杂度是O(log(m+n))。 假设A和B的元素个数都大于k/2,我们将A[k/2-1]和B[k/2-1]进行比较，有以下三种情况： A[k/2-1] < B[k/2-1] A[k/2-1] > B[k/2-1] A[k/2-1]==B[k/2-1] 如果A[k/2-1] < B[k/2-1]，意味着A[k/2-1] 不可能大于A+B的第k大元素。因此，我们可以放心的删除A数组的这k/2个元素。 同理，当A[k/2-1] > B[k/2-1]，可以放心的删除B数组的这k/2个元素。 当A[k/2-1]==B[k/2-1]时，说明找到了第k大的元素，直接返回A[k/2-1]或B[k/2-1]即可。 因此，我们可以写一个递归函数。 当A或B是空时，直接返回A[k-1]或B[k-1]; 当k=1时，返回(A[0],B[0]); 当A[k/2-1]==B[k/2-1]时，返回A[k/2-1]或B[k/2-1]。
以下代码使用方法三。
class Solution { public: double findMedianSortedArrays(vector<int> A,vector<int> B) { int m=A.size(); int n=B.size(); int total=m+n; if(total%2) return find_kth(A.begin(),m,B.begin(),n,total/2+1); else return (find_kth(A.begin(),m,B.begin(),n,total/2)+find_kth(A.begin(),m,B.begin(),n,total/2+1))/2.0; } private: int find_kth(vector<int>::iterator A,int m,vector<int>::iterator B,int n,int k) { if(m>n) return find_kth(B,n,A,m,k); if(m==0) return *(B+k-1); if(k==1) return min(*A,*B); int ia=min(k/2,m),ib=k-ia; if(*(A+ia-1)<*(B+ib-1)) return find_kth(A+ia,m-ia,B,n,k-ia); else if(*(A+ia-1)>*(B+ib-1)) return find_kth(A,m,B+ib,n-ib,k-ib); else return *(A+ia-1); } };