LeetCode 004 Median of Two Sorted Arrays

题目描述：Median of Two Sorted Arrays

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

分析：

题目中的数组A和数组B都是排好序的，首先想到的算法是：设置一个计数器m，指针pA指向数组A的首地址，指针pB指向数组B的首地址。如果数组A的当前元素小，pA++，m++；如果数组B的当前元素小，pB++，m++。算法的复杂度是O(m + n)。

但是题目要求时间复杂度是O(log (m+n))，一有对数，就要用到二分法了+_+每次都排除数组一半的元素，就是O(log (m+n))了！

假设A和B的元素都大于k/2，那么比较两个数组中间的元素，即A[k/2 - 1]和B[k/2 - 1]。会有三种情况：

① A[k/2 - 1] == B[k/2 - 1]

② A[k/2 - 1] < B[k/2 - 1]

③ A[k/2 - 1] > B[k/2 - 1]

情况①，找到了第k大的元素，直接返回A[k/2 - 1]或B[k/2 - 1]；

情况②，A[k/2 - 1] < B[k/2 - 1]，则说明A[0]到A[k/2 - 1]不会出现第k大的元素，狠心排除掉；

情况③，A[k/2 - 1] > B[k/2 - 1]，则说明B[0]到B[k/2 - 1]不会出现第k大的元素，狠心排除掉。

递归函数：

• 当 A 或 B 是空时，直接返回 B[k-1] 或 A[k-1] ；
• 当 k=1 是，返回 min(A[0], B[0]) ；
• 当 A[k/2-1] == B[k/2-1] 时，返回 A[k/2-1] 或 B[k/2-1]

代码如下：

class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        
        int total = m + n;
        
        if(total & 0x1) return find_kth(A, m, B, n, total / 2 + 1);
        else return (find_kth(A, m, B, n, total / 2)
                        + find_kth(A, m, B, n, total / 2 + 1))/2.0;
        
    }
    
private:
    static int find_kth(int A[], int m, int B[], int n, int k){
        
        //always assume that m is equal or smaller than n
        if(m > n) return find_kth(B, n, A, m, k);
        if(m == 0) return B[k-1];
        if(k == 1) return min(A[0], B[0]);
        
        //divide k into two parts
        int ia = min(k / 2, m), ib = k - ia;
        
        if (A[ia - 1] < B[ib - 1])
            return find_kth(A + ia, m - ia, B, n, k - ia);
        else if (A[ia - 1] > B[ib - 1])
            return find_kth(A, m, B + ib, n - ib, k - ib);
        else
            return A[ia - 1];
    }
};