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

一.题目描述
NC36在两个长度相等的排序数组中找到上中位数
题目链接：https://www.nowcoder.com/practice/6fbe70f3a51d44fa9395cfc49694404ftpId=196&&tqId=37141&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking
给定两个有序数组arr1和arr2，已知两个数组的长度都为N，求两个数组中所有数的上中位数。
上中位数：假设递增序列长度为n，若n为奇数，则上中位数为第n/2+1个数；否则为第n/2个数
二.算法(无脑暴力)
求上中位数可以将两个数组利用vector进行合并，然后利用sort进行排序，在排序后的数组中找出上中位数，代码如下：

class Solution {
public:
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        int len = arr1.size()+arr2.size();
        int mid=0;
        //求出合并后中位数的下标
        if(len%2==0){
            mid=len/2;
        } else {
            mid=len/2+1;
        }
        vector<int>q;//为合并后的新数组
        for(int i=0;i<arr1.size();i++) q.push_back(arr1[i]);
        for(int i=0;i<arr2.size();i++) q.push_back(arr2[i]);
        sort(q.begin(),q.end());//补充一下：sort的复杂度是o(n*logn) 所以这一题也是勉强卡过去了
        int ans=0;
        ans=q[mid-1];//注意下标要减去1
        return ans;
    }
};
时间复杂度:o(n*log(n)) 对所以元素遍历，而且sort排序效率可以达到log(n)
空间复杂度:o(n)需要开辟空间存储
优缺点：方便实现 但是空间复杂度高

三.算法(双指针)

首先求出上中位数的下标，然后在合并的过程中求出下标对应的数，下面是代码:

class Solution {
public:
    /**
     * find median in two sorted array
     * @param arr1 int整型vector the array1
     * @param arr2 int整型vector the array2
     * @return int整型
     */
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        int len = arr1.size()+arr2.size();
        int mid=0;
        //上中位数的下标
        if(len%2==0){
            mid=len/2;
        } else {
            mid=len/2+1;
        }
        int cnt=0;//表示合并数组的指针
        int ans=0;
        int a=0,b=0;//a,b分别表示数组arr1,arr2的下标指针
        while(cnt!=mid){
            if(arr1[a]<=arr2[b]){
                ans=arr1[a];
                a++;//指针后移
            } else{
                ans=arr2[b];
                b++;//指针后移
            }
            cnt++;
        }
        return ans;
    }
};

时间复杂度：o(n)
空间复杂度：o(1) 不需要额外空间
优缺点：时间复杂度低，但是实现起来复杂