By

文章目录

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

找到两个有序数组的中位数，LeetCode第二题，但是难度远大于第一题

正常思路会想到，将两个数组归并，返回中间数。归并操作耗时O(m+n),显然达不到题目要求。
那么就要深挖题目中的条件。数组有序，往往会联想到二分的思路，每次排除掉一半的结果集。在这道题中，可以利用“寻找第k小的数”的思路，这样本题转化为寻找第(m+n)/2小的数：

先来看下两个有序数组中，寻找第k小的数的做法:
不妨假设两个数组升序排列，且长度均大于k/2，则我们比较AB中第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]时，在AB数组归并后，A[0]至A[k/2-1]之间的数必定都在B[k/2-1]的左边，也就是说我们可以排除掉这么长一段结果集，继续在剩下的元素组成的序列中寻找第(k - k/2)大小的数。
由于每次排除掉k/2，也就是(m+n)/4大小的结果集，所以此方式下，时间复杂度为O(log(m+n))

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
public double findMedianSortedArrays(int A[], int B[]) {
    int sum = A.length + B.length;
    if (sum % 2 != 0) {
        return findKth(A, 0, A.length - 1, B, 0, B.length - 1, sum / 2 + 1);
    } else {
        return (findKth(A, 0, A.length - 1, B, 0, B.length - 1, sum / 2)
                + findKth(A, 0, A.length - 1, B, 0, B.length - 1, sum / 2 + 1)
        ) / 2.0;
    }
}

private int findKth(int A[], int startA, int endA,
                    int B[], int startB, int endB,
                    int k) {
    int m = endA - startA + 1;
    int n = endB - startB + 1;
    if (m > n) return findKth(B, startB, endB, A, startA, endA, k); //只考虑a <= b的情况
    if (m < 1) return B[startB + k - 1];
    if (k == 1) return Math.min(A[startA], B[startB]);

    int midA = Math.min(k / 2, m), midB = k - midA;
    //如果a的第midA大的元素比b的第midB大的元素小，
    //那么删掉a的前midA个元素，在剩余的数中找第k-midA大的。
    if (A[startA + midA - 1] < B[startB + midB - 1])
        return findKth(A, startA + midA, endA, B, startB, endB, k - midA);
    else if (A[startA + midA - 1] > B[startB + midB - 1])
        return findKth(A, startA, endA, B, startB + midB, endB, k - midB);
    else
        return A[startA + midA - 1];
}
文章目录