LintCode (65) Median of two sorted array

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.

Have you met this question in a real interview? 

Yes

Example

Given A=[1,2,3,4,5,6] and B=[2,3,4,5], the median is 3.5.

Given A=[1,2,3] and B=[4,5], the median is 3.

Challenge

The overall run time complexity should be O(log (m+n)).

截一半，这题好难。。。就算刷过一次了，回过头来还是觉得难。。。。

不过用rotated array 的思路的话， 就好做些。

比如A 和B 等长， 求第k个， 比较A的第k/2和B的第k/2的值， 如果A[k/2] < B[ k/2] 那么久放弃A前k/2，反之，放弃B的前k/2， 但是具体操作的时候还是有出入。。。

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 32 33 34 35 36 37 38 39

class Solution { public: /** * @param A: An integer array. * @param B: An integer array. * @return: a double whose format is *.5 or *.0 */ double findMedianSortedArrays(vector<int> A, vector<int> B) { // write your code here int m=A.size(); int n=B.size(); int total=m+n; if (total%2==1){ return findK(A,0,A.size(), B, 0, B.size(), total/2+1); } else{ return (findK(A, 0, A.size(), B, 0, B.size(), total/2) +findK(A, 0, A.size(), B, 0, B.size(), total/2+1))/2.; } } int findK(vector<int>& A, int begA, int lenA, vector<int>& B, int begB, int lenB, int k){ if (lenA>lenB){ return findK(B,begB, lenB, A, begA, lenA, k); } if (lenA==0) return B[begB+k-1]; if (k==1){ return min(A[begA], B[begB]); } int midA= min(lenA, k/2); int midB= k-midA; if (A[begA+midA-1]<=B[begB+midB-1]){ return findK(A, begA+midA, lenA-midA, B, begB, lenB, k-midA); } else{ return findK(A, begA, lenA, B, begB+midB, lenB-midB, k-midB); } } };