LeetCode4:寻找两个有序数组的中位数

这个题目真的抽象

题目描述

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

中位数需要满足两个条件:

1.左侧和右侧数量相等

2.比左侧数的最大值大,比右侧数最小值小

LeetCode4:寻找两个有序数组的中位数

 

 因此当我们在某个数组中找到某个位置i之后,由于性质1,它在另一个数组中的位置j也确定下来了,0~i与0~j的元素个数和要等于i+1~end和j+1~end的元素个数和(当然这是在偶数情况下,奇数情况下会相差1)

此时如果满足性质2,则我们要找的中位数的位置就确定下来了。

现在假设在A中找到了位置i,如果此时满足max(A[i-1],B[j-1])<=min(A[i],B[i]),则这个位置就一定是中位数的分界点,因为max(~)代表左侧数组的最大值,min(~)代表右侧数组的最小值,如果左侧最大的小于右侧最小的,则这个分界位置一定是中位数的分界线。

我们让i为“空隙”而不是真正指向的数,意思就是i是A[i-1]与A[i]间的位置而不是A[i]或A[i-1],这样,对于一个有m个数的数组,共有m+1个划分位置。

对于另一个数组中的j,我们由i+j=m-i+n-j =======>j=(m+n)/2-i;(i代表i左侧有i个数,j代表j左侧有j个数;m-i代表i+1~m间共有m-i个数,n-j代表j+1~n间共有n个数)

这个公式当然不能适应于所有情况,当m+n为偶数时,这个公式刚好能把两组数分成大小相等的两堆,但当m+n为奇数时,左侧堆一定会比右侧堆少1个。

但这并不要紧,因为要找的只是i的位置,即使奇数时左侧堆比右侧的堆少一个,我们用if else来分情况讨论就好了。

另外,i一定是数组个数少的那个数组的索引,因为如果i是长数组的索引,则j=(m+n)/2-i可能小于0。

在得到这个思路后,我们可以用二分法来解决这个问题。

当B[j-1]>A[i]时,说明i取的太小,应该将i增大,令low=i+1;

当A[i-1]>B[j]时,说明j取的太大,应该缩小i,令high=i-1;

另外对于边界情况,比如i=0时,起始这时i-1已经不存在了,只要比较B[j-1]与A[i]就好了。

 

当找到i位置后,进行分类讨论即可。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
		if(nums1.empty()||nums2.empty())
		{
			auto& arr=nums1.empty()?nums2:nums1;
			int l=0,h=arr.size()-1;
			int i=(l+h)/2;
			if(arr.size()%2==0)
			{
				return ((double)arr[i]+(double)arr[i+1])/(double)2;
			}
			else
			{
				return arr[i];
			}
		}
        auto& sarr=nums1.size()>nums2.size()?nums2:nums1;
		auto& larr=(sarr==nums2)?nums1:nums2;
		int l=0,h=sarr.size();
		int i=(l+h)/2;
		while(l<h)
		{
			int j=(nums1.size()+nums2.size())/2-i;
			if(i==0)
			{
				int val=larr[j-1];
				if(val<=sarr[i])
					break;
				else
					l=i+1;
			}
			else if(i==sarr.size())
			{
				int lvs=sarr[i-1];
				if(lvs<=larr[j])
					break;
				else
					h=l-1;
			}
			else
			{
				int lvs=sarr[i-1];
				int rvs=sarr[i];
				int lvl=larr[j-1];
				int rvl=larr[j];
				if((lvs<=rvl)&&(lvl<=rvs))
					break;
				else if(lvs>rvl)
					h=i-1;
				else
					l=i+1;
			}
			i=(l+h)/2;
		}
		i=(l+h)/2;
		int len=nums1.size()+nums2.size();
		int j=(nums1.size()+nums2.size())/2-i;
		double ans;
		if(i==0)
		{
			if(len%2==0)
			{
				double rv=(j==larr.size())?sarr[i]:min(sarr[i],larr[j]);
				ans=(rv+(double)larr[j-1])/2;
			}
			else
			{
				ans=min((double)sarr[i],(double)larr[j]);
			}
		}
		else if(i==sarr.size())
		{
			if(len%2==0)
			{
				double lv=(j==0)?sarr[i-1]:max(sarr[i-1],larr[j-1]);
				ans=(lv+(double)larr[j])/2;
			}
			else
			{
				ans=max((double)sarr[i-1],(double)larr[j]);
			}
		}
		else
		{
			if(len%2==0)
			{
				ans=(max((double)sarr[i-1],(double)larr[j-1])
					+min((double)sarr[i],(double)larr[j]))/2;
			}
			else
			{
				ans=min((double)sarr[i],(double)larr[j]);
			}
		}
		return ans;
    }
};

  

 

上一篇:用Python3写一个中国象棋游戏


下一篇:数字货币:Tether市值最近几周大幅飙升,或推动比特币价格反弹接近历史高点