题目：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 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

示例 3：
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

我的方法一：双指针，O(N) O(1)

步骤

1. 如果将两个vector合并，中位数就是中间两个元素的和平均或者中间一个元素的值；
2. 由于合并vector会产生O(N)的空间复杂度，我们其实可以使用两个指针分别指向两个vector，来模拟合并的过程；
3. 我们很容易知道中位数对应的合并后的vector对应的位置
4. 所以用两个指针index1和index2开始遍历两个vector，较小的元素对应的index往后一位，当移动的总数和中位数对应的位置匹配时就停止；

复杂度

时间复杂度：O(N)，因为遍历两个vector总和的一半；
空间复杂度：O(1)，没有合并两个vector；

边界条件

1. 当两个vector长度都为0时，直接返回0；
2. 有可能一个vector特别短，一个特别长，会出现一个vector已经遍历完了，还没有找到对应的中位数；

代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int total = nums1.size() + nums2.size();
        if(total == 0){
            return 0;
        }

        int left = (total - 1) / 2;
        int right = total / 2;
        double ret = 0;

        int nums1_index = 0;
        int nums2_index = 0;
        int nums1_size = nums1.size();
        int nums2_size = nums2.size();
        int index = 0;

        //时间复杂度O(N+M)，空间复杂度O(1)
        while(nums1_index < nums1_size || nums2_index < nums2_size){
            if(nums1_index < nums1_size && nums2_index < nums2_size){
                if(nums1[nums1_index] < nums2[nums2_index]){
                    if(index == left){
                        ret = nums1[nums1_index];
                    }
                    if(index == right){
                        ret += nums1[nums1_index];
                        break;
                    }
                    nums1_index++;
                }else{
                    if(index == left){
                        ret = nums2[nums2_index];
                    }
                    if(index == right){
                        ret += nums2[nums2_index];
                        break;
                    }
                    nums2_index++;
                }
            }else if(nums1_index < nums1_size){
                if(index == left){
                    ret = nums1[nums1_index];
                }
                if(index == right){
                    ret += nums1[nums1_index];
                    break;
                }
                nums1_index++;
            }else {
                if(index == left){
                    ret = nums2[nums2_index];
                }
                if(index == right){
                    ret += nums2[nums2_index];
                    break;
                }
                nums2_index++;
            }
            
            index++;
        }

        return ret / 2;
    }
};

更优的方法

二分查找 O(logn)

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/