1.题目描述
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
2.示例
示例 1：
输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [0,0], nums2 = [0,0] 输出：0.00000
示例 3：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
3.分析
此题难度不大，有如下思路
（1）最简单的想法是，将一个数组的每一个元素，按照升序通过插入法等方法将两个数组合并。然后根据奇偶性质找出中位数的位置并计算。
但是这种方法不是高效的，空间上它需要重新申请一个m+n长度的新数组。至少也需要将较短的那个数组重新申请空间到较长的那个数组上。
时间上，由于每次需要将一个元素有序插入到另一个数组中，时间也会有较大的浪费。
（2）根据上面的方法，时间浪费的原因在于没有利用好两个数组已经有序的条件。改进的方法，不再将两个数组和并，也不关心中位数之后的元素
的排序。通过两个数组的元素和计算出中位数的位置，设置指向两个数组的两个游标进行移动。在两个数组的元素都没被遍历完时，比较当前两个游标对应的元素大小，使较小元素的游标后移。
在某一个数组已经被比较完时，则将另一个数组的元素顺序不动遍历即可，直到整体的游标数到达中位数的位置。
这样就提高了时间和空间的效率，类似流的不保存元素的值，只关心中位数的位置。达到了空间复杂度为O(m+n)
4.代码
class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int total = nums1.size() + nums2.size();//总元素数 int numPos1 = 0;//数组1的游标 int numPos2 = 0;//数组2的游标 int counter = 0;//计数器 float result =0;//结果值 if(total%2!=0){//奇数 while(counter<total/2){ if(numPos1<nums1.size()&&numPos2<nums2.size()){ if(nums1.at(numPos1)<nums2.at(numPos2)) numPos1++; else numPos2++; } else if(numPos1<nums1.size()) numPos1++; else numPos2++; counter++; } if(numPos1<nums1.size()&&numPos2<nums2.size()){ if(nums1.at(numPos1)<nums2.at(numPos2)) result+=nums1.at(numPos1); else result+=nums2.at(numPos2); } else if(numPos1<nums1.size()) result+=nums1.at(numPos1); else result+=nums2.at(numPos2); }else{//偶数 while(counter<total/2-1){ if(numPos1<nums1.size()&&numPos2<nums2.size()){ if(nums1.at(numPos1)<nums2.at(numPos2)) numPos1++; else numPos2++; } else if(numPos1<nums1.size()) numPos1++; else numPos2++; counter++; } for(int i=0;i<2;i++){ if(numPos1<nums1.size()&&numPos2<nums2.size()){ if(nums1.at(numPos1)<nums2.at(numPos2)) {result+=nums1.at(numPos1);numPos1++;} else {result+=nums2.at(numPos2);numPos2++;} } else if(numPos1<nums1.size()) {result+=nums1.at(numPos1);numPos1++;} else {result+=nums2.at(numPos2);numPos2++;} } result =result/2; } return result; } };
5.总结
（1）上述代码不够优雅，原因是一开始就将奇偶分开处理，导致有很大程度的重复代码。
（2）这也说明了这个题的细节问题：即对奇偶元素个数的游标位置的处理细节。