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

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

http://www.nowcoder.com/practice/6fbe70f3a51d44fa9395cfc49694404f

题意概述

给定两个长度相等的有序数组
要求找到找到两个数组中所有数的上中位数
上中位数：假设递增序列长度为n，若n为奇数，则上中位数为第n/2+1个数；否则为第n/2个数

方法一：暴力

思路与具体做法

将两个数组合并为一个数组然后排序直接返回其上中位数的位置

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

时间复杂度和空间复杂度分析

时间复杂度： $O(n\log_{2}{n} )$ ：总共遍历了长度为 $n$ 的数组，然后对其排序，sort时间复杂度类比快排 $O(n\log_{2}{n} )$
空间复杂度： $O (1)$ : 没有申请额外的空间

方法二：双指针

思路与具体做法

两个指针分别指向两个数组的首段元素
每次记录两个指针指向的较小的元素，并令对应数组指针自增加一
因为两数组长度相同，所以总共遍历元素数目等于一个数组长度时，即找到了中位数

class Solution {
public:
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
		int i=0,j=0,n=arr1.size(),ans;//i，j作为双指针指向两个数组首端元素 
		while(i+j<n){//到遍历过的总元素i+j等于总数组长度一半n时，即找到中位数 
			if(arr1[i]<arr2[j])ans=arr1[i++];//ans每次记录较小值，并令指针后移 
			else ans=arr2[j++];	
		} 
		return ans;//返回中位数 
    }
};

时间复杂度和空间复杂度分析

时间复杂度： $O (n)$ ：总共遍历了长度为n的数组
空间复杂度： $O (1)$ : 没有申请额外的空间

方法三：双二分法

思路与具体做法

因为是两个长度相同的有序数组，如果能分别将两个数组从中间裂开，使得两个数组的左半部分总长与右半部分总长相等，那么我们要找的上中位数一定就只与中间裂开处的四个数组元素有关
不断对两个数组同时进行二分查找，并计算各自的中位数
如果各自的中位数相等，即满足上述的分别断开，两个数组的左半部分总长与右半部分总长相等，此时直接返回即可
否则取较小中位数的右半部分（长度为偶数的子区间中位数后一位才是右半部分的起点），较大中位数的左半部分，继续双二分法
最后返回排序后中位数两个数中的最小值即为上中位数

class Solution {
public:
    int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) {
        int l1=0,r1=arr1.size()-1,l2=0,r2=r1;//两个数组的左右端点
		int mid1=0,mid2=0;//两个数组的中位数
		while(l1<r1){
			mid1=l1+(r1-l1)/2,mid2=l2+(r2-l2)/2;//计算得到的中位数
			int flag=(r1-l1)%2;//标记数组长度的奇偶 
			if(arr1[mid1]==arr2[mid2])return arr1[mid1];//当两个序列中位数相等的情况下，直接返回中位数 
			else if(arr1[mid1]<arr2[mid2])l1=mid1+flag,r2=mid2;//不相等，则更新查找区间为小数的右区间和大数的左区间，因为偶数下取整，所以加一作为右区间左边界 
			else l2=mid2+flag,r1=mid1;
		} 
		return min(arr1[l1],arr2[l2]);//排序后中间的两个数
    }
};