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

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

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

一、归并算法

合并两个有序数组，再根据长度直接得到中位数。时间复杂度不符合要求。

其实可以不用全部合并完，合并到中位数的位置即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int i = 0;
        int j = 0;
        int k = 0;
        int[] tmp = new int[len1 + len2];
        while (i < len1 && j < len2) {
            tmp[k++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
        }
        while (i < len1) {
            tmp[k++] = nums1[i++];
        }
        while (j < len2) {
            tmp[k++] = nums2[j++];
        }
        return k % 2 == 0 ? (tmp[(k - 1) / 2] + tmp[k / 2]) / 2.0 : tmp[k / 2];
    }
}

二、二分搜索

主要思路：用分割线分割两个数组，保证nums1中分割线左边的第一个元素小于等于nums2中分割线右边的第一个元素；nums1中分割线右边的第一个元素大于等于nums2中分割线左边的第一个元素。

简单来说就是两个数组分割线左边的元素小于等于分割线右边的元素。

我们只需要对长度较小的数组进行二分即可。另一个数组对应的分割线位置可以通过计算得到。

如下图：分割线左边的8大于右边的6，因此分割线偏左，需要向右调整。

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
47
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            int[] t = nums1;
            nums1 = nums2;
            nums2 = t;
        }

        int m = nums1.length;
        int n = nums2.length;
        
        // 分割线左边的所有元素的个数
        int totalLeft = m + (n - m + 1) / 2;

        // 在 nums1 的区间 [0, m] 里查找恰当的分割线，
        // 使得 nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums1[i]
        int left = 0;
        int right = m;

        while (left < right) {
            // i表示nums1中分割线右边的第一个元素，j表示nums2中分割线右边的第一个元素
            int i = left + (right - left + 1) / 2;
            int j = totalLeft - i;
            // 说明nums1中分割线偏右，需调整，下一轮搜索区间：[left, i - 1]
            if (nums1[i - 1] > nums2[j]) {
                right = i - 1;
            } else {
                // 下一轮搜索区间：[i, right]
                left = i;
            }
        }

        int i = left;
        int j = totalLeft - i;

        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];

        if((m + n) % 2 == 1) {
            return Math.max(nums1LeftMax, nums2LeftMax);
        } else {
            return (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) * 0.5;
        }
    }
}

参考题解：https://suanfa8.com/binary-search/solutions/find-index/0004-median-of-two-sorted-arrays/

https://leetcode.cn/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/