描述

给定已经排序的两个数组，找到这两个数组中所有元素的第k大的数字。

分析及实现

最直观的方法是把两个数组合并为一个有序数组，然后返回第k大的数字，这种方法的时间、空间复杂度都是O(m+n)；

我们需要的是第k大的数字，不需要进行合并这么复杂的操作，可以使用两个游标分别指向两个数组，每次取两个游标里比较小的值，直到取到第k次，即可获取到第k大数字。此种操作方式的时间复杂度为O(m+n)，空间复杂度为O(1)。

有没有更好的方法呢？在有序数组中查找不使用二分查找总是遗憾的。在一个有序数组中查找元素是获取数组的中间元素，然后和目标值进行比较，现在在两个有序数组中查找的关键问题是如何使用二分查找呢？

假设数组A和数组B的元素个数都大于k/2，我们将A的第k/2个和B的第k/2个元素进行比较，有三种情况：

1，A[k/2-1] == B[k/2-1];

2，A[k/2-1] > B[k/2-1];

3，A[k/2-1] < B[k/2-1];

对于第1种情况，已经找到第k个元素了，返回A[k/2-1]或者B[k/2-1]即可；

对于第2种情况，B[0] ~ B[k/2-1]一定在第k个元素前面，可以在下次查找时排除掉；

对于第3种情况，A[0] ~ A[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]时，返回二者之一即可；

代码实现如下：

int findTheKthElementInTwoSortedArray01(int A[], int m, int B[], int n, int kth)
{
    if (kth > (m+n)) {
        return -1;
    }
    if(m > n) {
        return findTheKthElementInTwoSortedArray01(B, n, A, m, kth);
    }
    if (kth == 1) {
        return std::min(A[0], B[0]);
    }
    if (m == 0) {
        return B[kth-1];
    }
    
    //分割k
    int ia = std::min(kth/2, m);
    int ib = kth - ia;
    
    if (A[ia-1] < B[ib-1]) {
        return findTheKthElementInTwoSortedArray01(A+ia, m-ia, B, n, kth-ia);
    }
    if (A[ia-1] > B[ib-1]) {
        return findTheKthElementInTwoSortedArray01(A, m, B+ib, n-ib, kth-ib);
    }
    
    return A[ia-1];
}

代码在这儿