题目主要信息:

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

具体思路:

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

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

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

代码实现:

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),无额外辅助空间,常数级变量