4. 寻找两个正序数组的中位数

这是LeetCode热题100的第4题 4.两个有序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

1
2
3
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

1
2
3
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106

解法：

定义做法

中位数是数组最中间的数，我们可以合并数组然后来找到最中间的数

直接合并

把某一个数组连接到另一个后面，然后排序，取得中位数

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public double findMedianSortedArrays(int[] a, int[] b) {
        int m = a.length, n = b.length;
        int all = m + n;
        int[] res = new int[m + n];
        System.arraycopy(a, 0, res, 0, m);
        System.arraycopy(b, 0, res, m, n);
        Arrays.sort(res);
        if (all % 2 == 1) return res[all / 2];
        return (res[all / 2 - 1] + res[all / 2]) / 2.0;
    }
}
归并

由于两个数组已经有序，所以可以参考归并排序的办法来进行两个数组的合并，并且之后不需要排序，比直接合并然后排序的复杂度优

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public double findMedianSortedArrays(int[] a, int[] b) {
        int m = a.length, n = b.length;
        int all = m + n;
        int[] res = new int[m + n];
        int p1 = 0, p2 = 0, p = 0;
        while (p1 < m && p2 < n) {
            res[p++] = a[p1] < b[p2] ? a[p1++] : b[p2++];
        }
        while (p1 < m) res[p++] = a[p1++];
        while (p2 < n) res[p++] = b[p2++];

        if (all % 2 == 1) return res[all / 2];
        return (res[all / 2 - 1] + res[all / 2]) / 2.0;
    }
}

二分

由于中位数是整个数组中第k个数，那么位置在 k - 1之前的数不可能是中位数

如何判断位置？可以考虑比它小的数的个数有多少

  • 看两个数组中的 k / 2的位置
  • 哪一个小，说明它以及之前的数都不可能是中位数，可以排除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    private double get(int[] a, int x, int[] b, int y, int k) {
        int m = a.length, n = b.length;
        if (x == m) return b[y + k - 1];
        if (y == n) return a[x + k - 1];
        if (k == 1) return Math.min(a[x], b[y]);

        int p1 = Math.min(m, x + k / 2) - 1;
        int p2 = Math.min(n, y + k / 2) - 1;

        if (a[p1] <= b[p2]) return get(a, p1 + 1, b, y, k - (p1 - x + 1));
        return get(a, x, b, p2 + 1, k - (p2 - y + 1));
    }
    public double findMedianSortedArrays(int[] a, int[] b) {
        // k
        // a k / 2
        // b k / 2
        int m = a.length, n = b.length;
        int all = m + n;
        if (all % 2 == 1) return get(a, 0, b, 0, all / 2 + 1);
        double fi = get(a, 0, b, 0, all / 2), se = get(a, 0, b, 0, all / 2 + 1);
        return (fi + se) / 2;
    }
}