LeetCode-04 Median of Two Sorted Arrays

题目：Median of Two Sorted Arrays
描述：There are two sorted arrays nums1 and nums2 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)).

　　这个题要求“两个有序数组的中位数”，我们可以推广到求“两个有序数组的第k小的数(findKth)”。题目要求算
法的时间复杂度为O(log (m+n))，很明显不能简单地进行归并，这种时间复杂度容易联想到二分查找的思
想。findKth关键思想如下：

  1. 开始时检测边界条件(数组长度是否为0，k是否为0)
  2. 从数组A中取中间某个位置aMid = aLen * k / (aLen + bLen)，取数组B中位置bMid = k - aMid
  3. 比较A[aMid]和B[bMid]大小，如果A[aMid]<B[bMid]，排除掉数组A中aMid之前的元素和数组B中bMid之后的元素，
    反之则排除掉数组B中bMid之前的元素和数组A中aMid之后的元素，同时更新K值
  4. 递归调用findKth，从缩减后的两个有序数组中寻找第K小的数
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
40
41
42
43
44
45
46
public static double findMedianSortedArrays(int A[], int B[]) {
    int m = A.length;
    int n = B.length;
 
    if ((m + n) % 2 != 0)
        return (double) findKth(A, B, (m + n) / 2, 0, m - 1, 0, n - 1);
    else {
        return (findKth(A, B, (m + n) / 2, 0, m - 1, 0, n - 1) 
            + findKth(A, B, (m + n) / 2 - 1, 0, m - 1, 0, n - 1)) * 0.5;
    }
}
 
public static int findKth(int A[], int B[], int k, 
    int aStart, int aEnd, int bStart, int bEnd) {
 
    int aLen = aEnd - aStart + 1;
    int bLen = bEnd - bStart + 1;
 
    // 边界
    if (aLen == 0)
        return B[bStart + k];
    if (bLen == 0)
        return A[aStart + k];
    if (k == 0)
        return A[aStart] < B[bStart] ? A[aStart] : B[bStart];
 
    int aMid = (int)(1.0 * aLen / (aLen+bLen) * k); //用数组长对K做平均
    int bMid = k - aMid - 1;
 
    aMid = aMid + aStart;
    bMid = bMid + bStart;
 
    if (A[aMid] > B[bMid]) {
        k = k - (bMid - bStart + 1);
        aEnd = aMid;
        bStart = bMid + 1;
    } else if (A[aMid] < B[bMid]) {
        k = k - (aMid - aStart + 1);
        bEnd = bMid;
        aStart = aMid + 1;
    } else {
        return A[aMid];
    }
 
    return findKth(A, B, k, aStart, aEnd, bStart, bEnd);
}