题目:
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
题意已只两个有序的序列,找到他们的中位数,复杂度要求O(log (m+n))。
问题可以转化成两个有序序列找第num大的数,用类似二分的思想,用递归处理。
因为两个序列是有序的,对比A和B第num/2个数大小,每次把小的序列删掉num/2个数,能保证不会删掉第num大的数,可以纸上验证一下。
如果一个序列没有num/2个数,那么就比较两个序列第min(n,m)个数的大小,这么做能尽快删掉一个序列所有元素,结束递归。
这么做最坏情况复杂度是O(log (m+n)),也就是num递归到1。
double find(int A[],int m,int B[],int n,int del)
{
if(m==0)return B[del-1];
else if(n==0)return A[del-1];
else if(del==1)return A[0]<B[0]?A[0]:B[0];
int temp=del/2;
if(min(m,n)<temp)temp=min(m,n);
if(A[temp-1]>=B[temp-1])return find(A,m,B+temp,n-temp,del-temp);
else return find(A+temp,m-temp,B,n,del-temp);
} class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
int del=(n+m+1)/2;
double temp=find(A,m,B,n,del);
if((m+n)&1)return temp;
else return (find(A,m,B,n,del+1)+temp)/2.0;
}
};