【Leetcode 4】Median of Two Sorted Arrays

题意：给定两个有序的数组，求出中位数。

提供两种思路：

第一种思路理解起来比较简单效率为O(logn+logm)：

第二种思路效率为O（log(min(n,m))）

不过两种思路提交上去时间差不多，最好都为32ms

思路一  O(logn+logm)：按照求解第k大算法的思想。具体如下：

假设有两个数组 A,B  现要求两数组中所有数字的第k大，那么我们可以比较 A[k/2]和B[k/2]  假设 A[k/2]<B[k/2]那么A数组中  从[1,k/2-1]的所有数字都不可能是第k大，可以直接去掉。以此递归求解即可。效率为O(logn+logm)

注意:

1 注意数组边界

2总数为偶数时要注意判断

class Solution {
public:
	double getkth(vector<int> A, vector<int> B,int la,int ra,int lb,int rb,int k,int flag){
		if(ra<la){
			if(flag==0)
				return B[lb+k-1];
			else
				return (B[lb+k-1]+B[lb+k])*0.5;//总个数为偶数
		}
		if(rb<lb){
			if(flag==0)
				return A[la+k-1];
			else
				return (A[la+k-1]+A[la+k])*0.5;//总个数为偶数
		}
		if(k==1){
			if(flag==0)
				return min(A[la],B[lb]);
			else{//总个数为偶数
				if(A[la]<B[lb]){
					if(la+1>ra)return (A[la]+B[lb])*0.5;
					else
						return (A[la]+min(A[la+1],B[lb]))*0.5;
				}else{
					if(lb+1>rb)return (A[la]+B[lb])*0.5;
					else{
						return (B[lb]+min(A[la],B[lb+1]))*0.5;
					}
				}
			}
		}
		int mid1=min(ra,k/2+la-1);//注意边界不能超出
		int mid2=min(rb,k/2+lb-1);
		if(A[mid1]<=B[mid2]){
			return getkth(A,B,mid1+1,ra,lb,rb,k-(mid1-la+1),flag);//小的那一半无用
		}else{
			return getkth(A,B,la,ra,mid2+1,rb,k-(mid2-lb+1),flag);
		}

	}
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
		int n=nums1.size();
		int m=nums2.size();
		if((n+m)&1){
			return getkth(nums1,nums2,0,n-1,0,m-1,(n+m+1)/2,0);
		}else{
			return getkth(nums1,nums2,0,n-1,0,m-1,(n+m)/2,1);
		}
    }
};

提交结果：

思路二  O（log(min(n,m))）：对较短的数组进行二分，假设第一个数组A下标为x  求解第k大的话，那么比较B[k-x]与 A[x]  找出  A[x]<B[k-x]  &&A[x+1]>B[k-x-1]的分界线，然后再判断即可。（边界比较烦）效率为O（log(min(n,m))）

class Solution {
public:
	double gao(vector<int>& A, vector<int>& B,int n,int m){

		int l=0,r=n-1;
		int k=(n+m+1)>>1;
		int flag=((n+m)&1);
		if(n==0){
			if(flag)return B[k-1];
			else
				return (B[k]+B[k-1])*0.5;
		}
		while(r-l>1){
			int mid=(l+r)>>1;
			int x=k-mid-2;
			if(B[x]>A[mid])
				l=mid;
			else
				r=mid;
		}
		if(B[k-r-2]>A[r])
			l=r;
		int x=k-l-2;
		if(B[x]<A[l]){
			if(flag)return min(B[x+1],A[l]);
			else{
				if(B[x+1]<A[l]){
					if(x+2<m)
						return (B[x+1]+min(A[l],B[x+2]))*0.5;
					else
						return (B[x+1]+A[l])*0.5;
				}else{
					if(l+1<n)
						return (A[l]+min(A[l+1],B[x+1]))*0.5;
					else
						return (A[l]+B[x+1])*0.5;
				}

			}
		}else{
			if(l+1>=n)
			{
				if(flag)
					return B[x];
				else{
					return (B[x]+B[x+1])*0.5;
				}

			}
			if(flag){
				return min(B[x],A[l+1]);
			}else{
				if(B[x]<A[l+1]){
					if(x+1<m)
						return (B[x]+min(B[x+1],A[l+1]))*0.5;
					else
						return (B[x]+A[l+1])*0.5;
				}else{
					if(l+2<n)
						return (A[l+1]+min(B[x],A[l+2]))*0.5;
					else
						return (A[l+1]+B[x])*0.5;
				}
			}
		}


	}
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
		int n=nums1.size();
		int m=nums2.size();
		if(n>m)
			return gao(nums2,nums1,m,n);
		else
			return gao(nums1,nums2,n,m);
    }
};