寻找两个正序数组的中位数
时隔许久，我又回来了。
题目：给定两个大小分别为m和n的正序（从小到大）数组nums1和nums2。请你找出并返回这两个正序数组的中位数。
要求算法的时间复杂度为O(log(m+n))。
示例1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
题目链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
C++实现
方法一：
很朴素的想法，通过归并排序的思路将两个正序数组合并为一个数组data，再根据data所含个数的奇偶性分别返回相应的结果。
时间复杂度O(m+n)
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
//新开辟数组data，记录nums1和nums2合并后的有序数组
vector<int> data;
int i=0,j=0;
while(i<nums1.size()&&j<nums2.size())
{
if(nums1[i]<nums2[j]){
data.push_back(nums1[i++]);
}
else{
data.push_back(nums2[j++]);
}
}
while(i<nums1.size())
{
data.push_back(nums1[i++]);
}
while(j<nums2.size())
{
data.push_back(nums2[j++]);
}
double ret=0; //待返回的中位数
if(data.size()%2==1)
{
ret=data[data.size()/2];
}
else{
ret=(data[(data.size()-1)/2]+data[(data.size()-1)/2+1])/2.0;
}
return ret;
}
};
方法二：
借鉴官方题解，通过二分查找实现。时间复杂度O(log(m+n))。
m+n是奇数时，中位数是两个正序数组中的第(m+n)/2+1个元素（从1开始数）；
m+n是偶数时，中位数是两个正序数组中的第(m+n)/2和第(m+n)/2+1个元素的平均值。
因此主要问题是实现找到两个正序数组的第k个元素的函数findKth()，如下所示：
使用index1和index2分别记录删除部分元素后，num1和num2下标的偏移量。初始为0。
比较num1[k/2-1]和num2[k/2-1]，以num1[k/2-1]<num2[k/2-1]为例，反之同理。num1[k/2-1]左侧共k/2-1个元素，即使num2[k/2-1]左侧的k/2-1个元素均全部小于num1[k/2-1]时，num1[k/2-1]名次取到最大为k-1，无法成为第k个元素。因此num1[k/2-1]及其左侧的元素均可排除，即nums1[0]到nums1[k/2-1]。k相应减少k/2个元素。
由于存在删除元素后考虑位置发生偏移，因此需要加上相应的基准index1和index2。
要注意可能存在index*+k/2-1下标越界的情况：nextIndex1=min(index1+k/2-1,m-1)。如果某一个数组越界，直接返回另一个数组中的第k个元素。
示例分析：
num1={1，3，4，9}
num2={1，2，3，4，5，6，7，8，9}
找第k=(4+9)/2+1=7个元素
index1=0，index2=0，比较下标为k/2-1=2的两个数：num1[2]=4>num2[2]=3，于是num2[index2]到num2[index2+k/2-1]范围内的元素被排除。修改index2和k：index2=3，k=k-k/2=4。index1=0。
比较num1[index1+k/2-1]=num1[1]和num2[index2+k/2-1]=num2[4]：num1[1]=3<num2[4]=5。于是num1[0]到num1[1]范围元素被排除。修改index1和k：index1=2，k=k-k/2=2。index2=3。
比较num1[index1+k/2-1]=num1[2]和num2[index2+k/2-1]=num2[3]：num1[2]=4<num2[3]=4。于是num1[2]到num1[2]范围元素被排除。修改index1和k：index1=3，k=k-k/2=1。index2=3。
k==1时，返回num1[index1]和num2[index2]中较小的一个，结束循环。这里返回4即为所求第7个数。
代码：
class Solution {
public:
int findKth(vector<int>& nums1, vector<int>& nums2,int k) //找到两个正序数组的第k个元素
{
int m=nums1.size();
int n=nums2.size();
int index1=0,index2=0; //index1和index2分别记录num1和num2各自的偏移量
while(1)
{
//边界情况
if(index1==m){return nums2[index2+k-1];} //num1越界
if(index2==n){return nums1[index1+k-1];} //num2越界
if(k==1){return min(nums1[index1],nums2[index2]);}
//正常情况
int nextIndex1=min(index1+k/2-1,m-1); //下一个比较值下标，注意越界时删除元素变少
int nextIndex2=min(index2+k/2-1,n-1);
if(nums1[nextIndex1]<=nums2[nextIndex2])
{
k-=(nextIndex1-index1+1); //修改k
index1=nextIndex1+1; //删除num1中元素，修改index1
}
else{
k-=(nextIndex2-index2+1); //修改k
index2=nextIndex2+1; //删除num2中元素，修改index2
}
}
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m=nums1.size();
int n=nums2.size();
if((m+n)%2==1){return findKth(nums1,nums2,(m+n)/2+1);}
else{return (findKth(nums1,nums2,(m+n)/2)+findKth(nums1,nums2,(m+n)/2+1))/2.0;}
}
};
