题解 | #在两个长度相等的排序数组中找到上中位数#

题目主要信息:

• 有两个等长都为$nn$的递增数组，需要求两个数组中所有数的上中位数
• 上中位数即两个数组中第$nn$小的数字

具体思路:

我们需要找的上中位数即两个数组中的第$nn$小，那去掉前$n-1n-1$个较小值就可以找到。既然两个数组都是递增数组，那么可以依次从两个数组开头得到最小值，使用双指针同步开始。

• step 1：准备双指针，分别从两个数组的首部开始。
• step 2：一共需要遍历$n-1n-1$次，找到前$n-1n-1$个最小的数字，每次比较将较小值的指针后移。
• step 3：最后再一次比较得到的较小值就是上中位数。

具体过程可以参考下列图示：

代码实现:

class Solution {
public:
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        int n = arr1.size();
        int x = 0, y = 0; //双指针
        for(int i = 1; i < n; i++){ //去掉前n-1个最小的数
            if(arr1[x] < arr2[y]) //每次取出较小的值
                x++;
            else
                y++;
        }
        return arr1[x] < arr2[y] ? arr1[x] : arr2[y]; //第n个最小的数
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历一次从1到$nn$
• 空间复杂度：$O(1)O(1)$，无额外辅助空间，常数级变量