题意：找出两个已排好序数组(合并之后形成新数组)的中位数，要求复杂度为O(log(m+n))，m，n分别为两数组长度。
分析：1）首先想到的是先把两个数组合并，最暴力的方法就是合并之后再快排一次，复杂度O((m+n)log(m+n)),在leetcode上居然也能过；
2）遍历两个数组将其合并，再找出中位数，复杂度为O(m+n);
3)以上两种方法虽然都能通过，但不符合题意的时间复杂度要求。第三种解法是更通用的求第K大的算法。算法思想如下：
由于数组A、B都为有序的，类似于二分查找的思想，不妨假设A、B的长度都大于K/2，通过对比A[K/2]和B[K/2]的大小关系，我们可以找出K/2个肯定比第K大的数更小的数：I).当A[K/2]>B[K/2]时，说明B的前K/2个数肯定属于两数组合并后的前K个数；II).当A[K/2]<B[K/2]时，同理，A的前K/2个数属于两数组合并后的前K个数；III).A[K/2]==B[K/2]，说明A[K/2]==B[K/2]就是已经找到的第K大的数。程序可通过递归实现，注意边界条件的判断。
代码：
1)
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
nums1.insert(nums1.end(),nums2.begin(),nums2.end());
sort(nums1.begin(),nums1.end());
int n=nums1.size();
return n%2?nums1[n/2]*1.0:(nums1[n/2-1]+nums1[n/2])/2.0;
}
};
2)
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
vector<int> nums;
while(nums1.empty()==false&&nums2.empty()==false){
if(nums1.front()<nums2.front()){
nums.push_back(nums1.front());
nums1.erase(nums1.begin());
}else{
nums.push_back(nums2.front());
nums2.erase(nums2.begin());
}
}
if(nums1.empty()){
nums.insert(nums.end(),nums2.begin(),nums2.end());
}else if(nums2.empty()){
nums.insert(nums.end(),nums1.begin(),nums1.end());
}
sort(nums.begin(),nums.end());
int n=nums.size();
return n%2?nums[n/2]*1.0:(nums[n/2-1]+nums[n/2])/2.0;
}
};
3)
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int size=(nums1.size()+nums2.size());
if(size%2!=0) return findKth(nums1,nums2,size/2+1);
return (findKth(nums1,nums2,size/2+1)+findKth(nums1,nums2,size/2))/2;
}
double findKth(vector<int> a,vector<int> b,int k){
if(a.size()>b.size()) return findKth(b,a,k);
if(a.empty()) return b.at(k-1);
if(k==1) return a.at(0)<b.at(0)?a.at(0):b.at(0);
int pa=k/2<a.size()?k/2:a.size();
int pb=k-pa;
if(a[pa-1]<b[pb-1]){
a.erase(a.begin(),a.begin()+pa);
return findKth(a,b,k-pa);
}else if(a[pa-1]>b[pb-1]){
b.erase(b.begin(),b.begin()+pb);
return findKth(a,b,k-pb);
}else return a[pa-1];
}
};