题解 | #多数组中位数#

题目的主要信息：

给定两个升序的数组 arr1 和 arr2 ，求两个数组合并后的下中位数

注意：下中位数指在两个数组的数个数在偶数时取更小的

方法一：

先合并两个数组，然后再对合并后的数组排序，计算中位数的位置，最后直接返回中位数。

具体做法：

class Solution {
public:
    int getUpMedian(vector<int>& arr1, vector<int>& arr2) {
        for(int i=0;i<arr2.size();i++){//合并
            arr1.push_back(arr2[i]);
        }
        sort(arr1.begin(),arr1.end());//排序
        int n=arr1.size();//中位数位置
        return arr1[n/2-1];//返回中位数
    }
};

复杂度分析：

• 时间复杂度：$O(nlo{g}_{2}n)O(nlog\_2n)$，sort排序的时间复杂度为$O(nlo{g}_{2}n)O(nlog\_2n)$。
• 空间复杂度：$O(1)O(1)$，只用了常数空间。

方法二：

首先计算两个数组的中位数位置target，同时遍历两个数组，由于两个数组已经是升序排序的，所以每次我们两数相比取更小的，直到取到第target个数就结束循环。需要注意的是，如果在遍历过程中，有数组提前结束遍历，则在另一个数组中继续。 具体做法：

class Solution {
public:
    int getUpMedian(vector<int>& arr1, vector<int>& arr2) {
        int i = 0;//遍历arr1
        int j = 0;//遍历arr2
        int count = 0;
        int res = 0;
        int target = (arr1.size()+arr2.size())/2;
        while(i < arr1.size() || j < arr2.size()) {//遍历两个数组
            if (count == target) {//如果找到第target个数则结束循环
                break;
            }
            if (i == arr1.size()) {//arr1遍历完了则在arr2数组中继续
                res = arr2[j++];
            } else if (j == arr2.size()) {//arr2遍历完了则在arr1数组中继续
                res = arr1[i++];
            } else {//两个数组都没有遍历完
                if (arr1[i] > arr2[j]) {//取其更小的数
                    res = arr2[j++];
                } else {
                    res = arr1[i++];
                }
            }
              
            count++;
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，while循环遍历两个数组。
• 空间复杂度：$O(1)O(1)$，只用了常数空间，