LeetCode-Q4-寻找两个正序数组的中位数

发表于 更新于 分类于 阅读次数： Changyan： 本文字数： 3.4k 阅读时长 ≈ 6 分钟

LeetCode-Q4-寻找两个正序数组的中位数

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

  • 示例 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
  • 示例 3：
1
2
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
  • 示例 4：
1
2
输入：nums1 = [], nums2 = [1]
输出：1.00000
  • 示例 5：
1
2
输入：nums1 = [2], nums2 = []
输出：2.00000

提示：

1
2
3
4
5
6
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

进阶：你能设计一个时间复杂度为 $O(log (m+n))$ 的算法解决此问题吗？

思路

题目已经保证两个数组是正序的。考虑中位数定义：

  • 奇数个数，即第$\dfrac{(n+1)}{2}$个数
  • 偶数个数，即第$\dfrac{n}{2}$个数和第$\dfrac{n}{2}+1$个数

如果依次比较两个数组的最小值，那么在$O(m+n)$的时间复杂度下，可以获取中位数（一趟变量）。

但是考虑到题目需要的时间复杂度是$O(log (m+n))$。很显然这是一个二分法的提示。

递归

一次遍历就相当于去掉不可能是中位数的一个值，也就是一个一个排除。由于数列是有序的，其实我们完全可以一半儿一半儿的排除。假设我们要找第 k 小数，我们可以每次循环排除掉 k/2 个数，然后将要找的k值更新。每次都是取 k/2 的数进行比较，有时候可能会遇到数组长度小于 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
25
26
27
28
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int m = nums2.length;
    int left = (n + m + 1) / 2;
    int right = (n + m + 2) / 2;
    //将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。
    return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;  
}
    
    private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1 
        if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
        if (len1 == 0) return nums2[start2 + k - 1];

        if (k == 1) return Math.min(nums1[start1], nums2[start2]);

        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;

        if (nums1[i] > nums2[j]) {
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        }
        else {
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }

分治

如果把m分成0~i-1和i~m 两个部分，把n分成0~j-1和j~n 两个部分。

当 A 数组和 B 数组的总长度是偶数时，如果我们能够保证

  • 左半部分的长度等于右半部分 ，i + j = m - i + n - j , 也就是 j = ( m + n ) / 2 - i
  • 左半部分最大的值小于等于右半部分最小的值 $max(A [ i - 1 ] , B [ j - 1 ]))<= min(A [ i ] , B [ j ])$

那么，中位数就可以表示如下 (左半部分最大值 + 右半部分最小值)/ 2。

当 A 数组和 B 数组的总长度是奇数时，如果我们能够保证

  • 左半部分的长度比右半部分大 1， i + j = m - i + n - j + 1也就是 j = ( m + n + 1) / 2 - i
  • 左半部分最大的值小于等于右半部分最小的值 $max (A [i - 1 ] , B [ j - 1 ]) <= min (A [ i ] , B [ j ])$

那么，中位数就是左半部分最大值，也就是左半部比右半部分多出的那一个数。$max(A [ i - 1 ] , B [ j - 1 ])$

上边的第一个条件我们其实可以合并为 $j = ( m + n + 1) / 2 - i$，因为如果 $m+n$ 是偶数，由于我们取的是int值，所以加 1 也不会影响结果。当然，由于 $0<=i<=m$ ，为了保证 $0<=j<=n$，我们必须保证 $m<=n$，否则 j可能是负数。

对于第二个条件，奇数和偶数的情况是一样的，我们进一步分析。为了保证 $max(A [ i - 1 ] , B [ j - 1 ])<= min(A [ i ] , B [ j ])$，因为 A 数组和 B 数组是有序的，所以 $A [ i - 1 ] <= A [ i ],B [ i - 1 ] <= B [ i ]$这是天然的，所以我们只需要保证 $B[ j - 1 ] <= A [ i ]$和 $A [ i - 1 ] <= B [ j ]$ 。

所以我们分情况讨论：

  • $B[j - 1 ] > A [ i ]$，并且为了不越界，要保证 j != 0，i != m，很明显，我们需要增加 i
  • $A[i - 1 ] > B [ j ]$ ，并且为了不越界，要保证 i != 0，j != n, 很明显，我们需要减少 i

当然，这里选择i的方式是二分搜索。

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
public class MedianOfTwoSortedArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;
        if (nums1.length == 0 && nums2.length == 0) {
            throw new IllegalArgumentException("arrays must not all empty");
        }
        if (n1 > n2) {
            return findMedianSortedArrays(nums2, nums1);
        }
        int k = (n1 + n2 + 1)/2; // 数组1和数组2长度的中位数
        int left = 0;
        int right = n1;
        while(left < right){ // 二分查找 nums1
            int m1 = left +(right - left)/2;
            int m2 = k - (m1+1); // num2 的约束

            if (nums1[m1] < nums2[m2])
                left = m1 + 1;
            else
                right = m1;
        }
        int m1 = left;
        int m2 = k - left;
        int c1 = Math.max(m1 <= 0 ? Integer.MIN_VALUE : nums1[m1-1],
                m2 <= 0 ? Integer.MIN_VALUE : nums2[m2-1]);
        if ((n1 + n2) % 2 == 1) { // 奇数
            return c1;
        }
        int c2 = Math.min( m1 >= n1 ? Integer.MAX_VALUE :nums1[m1],
                m2 >= n2 ? Integer.MAX_VALUE : nums2[m2]);
        return (c1 + c2) * 0.5;
    }
}