[Leetcode] Median of Two Sorted Arrays

Median of Two Sorted ArraysMar 28 '116215 / 31527

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)).

» Solve this problem

很久前就见过这题，当时随便一想，以为自己想到了logN的方法。

前几天又看到，打算写一下。发现之前的想法不靠谱啊！！

之前是想：每次找m/2, n/2处。然后比来比去搞。思路错了。

后来参考了：http://blog.csdn.net/zxzxy1988/article/details/8587244

 

 

class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int total = n + m;
        
        if (total % 2 == 0) {
            return (findKth(A, m, B, n, total/2) + findKth(A, m, B, n, total / 2 + 1)) / 2;
        }
        else 
            return findKth(A, m, B, n, total / 2 + 1);
    }
    
    double findKth(int a[], int m, int b[], int n, int k) {
        if (m > n) return findKth(b, n, a, m, k);
        if (m == 0) return b[k-1];
        if (k == 1) return min(a[0], b[0]);
        
        int ia = min(k/2, m);
        int ib = k - ia;
        if (a[ia-1] < b[ib-1]) return findKth(a+ia, m - ia, b, n, k - ia);
        else  if (a[ia-1] > b[ib-1]) return findKth(a, m, b+ib, n - ib, k - ib);
        else return a[ia-1];
    }
};