题意：
给两个有序（升or降）的数组，求两个数组合并之后的中位数。
思路：
按照找第k大的思想，很巧妙。将问题的规模降低，对于每个子问题，k的规模至少减半。 考虑其中一个子问题，在两个有序数组中找第k大，我们的目的只是将k的规模减半而已，所以可以对比nums1[k/2]和nums2[k/2]的大小，假设nums1[k/2]<=nums2[k/2]，那么nums1[0~k/2]这部分必定在0~k之中，那么将这部分删去，k减半，再递归处理。这里面可能有一些细节问题要考虑：
1. 如果其中1个数组的大小不及k/2。
2. 如果k=1了，两个数组依然还有元素，那么nums1[0]和nums2[0]必有一个为第k大。
3. 如果数组大小n+m是奇数还是偶数
4. 每个子问题的n大还是m大。
复杂度：k规模每次要么减半，要么就是其中一个数组不够k/2，那么递归到下一次就O(1)解决了。所以复杂度O( logk )，而k=(n+m)/2，所以O( log(n+m) )。
class Solution {
public:
typedef vector<int>::iterator it;
int findKth(it seq1,int size1,it seq2,int size2,int k)
{
if(size1==) return seq2[k-];
if(size1>size2) return findKth(seq2,size2,seq1,size1,k);
if(k==) return min(*seq1,*seq2);
int p1=min(size1,k/); //保证p1<=p2
int p2=k-p1;
if(seq1[p1-]<seq2[p2-])
return findKth(seq1+p1,size1-p1, seq2,size2, k-p1);
else
return findKth(seq1,size1, seq2+p2,size2-p2, k-p2);
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n=nums1.size(), m=nums2.size();
if((n+m)&)
return findKth(nums1.begin(),n, nums2.begin(),m, (n+m+)/);
else
{
double a=findKth(nums1.begin(),n, nums2.begin(),m, (n+m)/);
double b=findKth(nums1.begin(),n, nums2.begin(),m, (n+m)/+);
return (a+b)/;
}
}
};
AC代码