两个有序数组合并找第k个元素

 

       暴力求解 ： O(m + n)

       限定时间复杂度：O(lg(m + n))

 

       思路：

       设定两个数组A , B  amid , bmid分别为a ,b的中点

       比较A[amid] 与 B[mid]的值。

       只考虑A[mid] <= B[mid]的情况，分析清了这一种，另一种则是一模一样的。

       那么可以得到：

      B[mid] 前面一定有 amid + bmid + 1个元素

      A[mid]后面一定有 (m + n) - (amid + bmid + 1) 个元素

      

      接下来，就要看 k 是位于B[mid]的前面还是后面了：

      1 . k <= (amid + bmid + 1) ： 那么这用情况就可以不用考虑bmid 及其后面的元素

       2. k >  (amid + bmid +1) ： 那么这种情况就不要考虑amid 及其之前的元素了，只要在

           A[mid]之后的元素中找第(k - (amid + 1)) 个元素。

      这样，一路递归下去，不就省去了很多无关的计算了吗？

 

     代码实现：

        

int FindKth(int A[], int aL, int aR, int B[], int bL, int bR, int k) {
//递归出口 左边没元素了，那么就只能从B中[bL ,BR]段中找第k个元素
        if (aL > aR) return B[bL + k - 1];
        if (bL > bR) return A[aL + k - 1];

        int aMid = (aL + aR) / 2;
        int bMid = (bL + bR) / 2;

        if (A[aMid] <= B[bMid]) {
//分析为了简单 与k 比较时直接用的amid !
            if (k <= (aMid - aL) + (bMid - bL) + 1) 
                return FindKth(A, aL, aR, B, bL, bMid - 1, k);
            else
                return FindKth(A, aMid + 1, aR, B, bL, bR, k - (aMid - aL) - 1);
        }
        else { // A[aMid] > B[bMid]
            if (k <= (aMid - aL) + (bMid - bL) + 1) 
                return FindKth(A, aL, aMid - 1, B, bL, bR, k);
            else
                return FindKth(A, aL, aR, B, bMid + 1, bR, k - (bMid - bL) - 1);
        }