思路:难题
定义C为A和B合并而成的sorted array
m+n 奇数时:median为C第 (m+n)/2+1 个数
m+n 偶数时:median为C第 (m+n)/2 和第 (m+n)/2+1 个数的平均
问题转化为:如果已知A、B,和任意1<=k<=m+n,找到C中第k个数。其中C=sorted(merge(A,B))
比较A,B中任意两个数字A[i],B[j]。假设A[i],B[j]为C中第i'和j'个数。
1. 如果A[i] < B[j]:
B[j] > A[0:i]以及B[j]>=B[0:j-1] => B[j] => j' >= i+j+2
A[i] >= A[0:i-1]以及A[i]最多比B[0:j-1]大 => i' <= i+j+1
k> i+j+1,A[0:i]可以排除
k<= i+j+1,B[j:n-1]可以排除
2. 如果A[i] > B[j]:和1正好相反
k > i+j+1,B[0:j]可以排除
k<= i+j+1,A[i:m-1]可以排除
3. 如果A[i] = B[j]:
A[i]>=A[0:i-1],A[i]>=B[0:j] => i' >= i+j+2
B[j]和A[i]的情况一样 j' >= i+j+2
k > i+j+1,A[0:i]可以排除(假如i' = i+j+2,k = i+j+2,由于A[i]=B[j]两者都可以为第i+j+2个数字,所以A[i]可以排除掉)
k <= i+j+1,B[j:n-1]可以排除
所以3可以合并到1中。
思路整理:
A[i] <= B[j]
k > i+j+1,搜索A[i+1:m-1]和B[0:n-1]中的第k-i-1个元素
k <= i+j+1,搜索A[0:m-1]和B[0:j-1]中的第k个元素
A[i] > B[j]
k > i+j+1,搜索A[0:m-1]和B[j+1:n-1]中的第k-j-1个元素
k <= i+j+1,搜索A[0:i-1]和B[0:n-1]中的第k个元素
base case:
如果搜索A[s:e]且s>e,即A搜索完了,则直接返回B[k-1]。
如果搜索B[s:e]且s>e,即B搜索完了,则直接返回A[k-1]。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | class Solution { public: double findMedianSortedArrays(int A[], int m, int B[], int n) { int mid = (m+n)/2; if((m+n)%2) // odd total length return (double)findKthNum(A, m, B, n, mid+1); else { int median1 = findKthNum(A, m, B, n, mid); int median2 = findKthNum(A, m, B, n, mid+1); return 0.5*((double)median1 + (double)median2); } } int findKthNum(int A[], int m, int B[], int n, int k) { if(m==0) return B[k-1]; if(n==0) return A[k-1]; int i = m/2, j = n/2; if(A[i]<=B[j]) { if(k>i+j+1) return findKthNum(A+i+1, m-i-1, B, n, k-i-1); else return findKthNum(A, m, B, j, k); } else { if(k>i+j+1) return findKthNum(A, m, B+j+1, n-j-1, k-j-1); else return findKthNum(A, i, B, n, k); } } }; |
No comments:
Post a Comment