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

二分查找#

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

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

示例 1：

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

示例 2：

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

思路

这一题我认为最主要的难点就是在时间复杂度O(log (m+n))，要求二分查找的情况下，如何在 A 里画一条分割线，在 B 里画一条分割线使得：

左边的元素总个数 等于 右边的元素总个数（如果是奇数，让左边多一个）。
左半边所有的数 都要小于 右半边所有的数。

因为 A 和 B 本身就是有序的，所以 A 左边的数本来就小于右边的数。我们只需要保证的是：

A 左边最大的数 <= B 右边最小的数
B 左边最大的数 <= A 右边最小的数

所以，我们可以像提线木偶般，在短的那个数组进行二分，为了保证左右元素总数各占一半，B 中的切分位置就自动确定了，最后检查十字交叉条件即可(知道了思路，还是挺简单的)

1
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
2
    if  len(nums1) > len(nums2) {
3
        return findMedianSortedArrays(nums2, nums1)
4
    }
5

6
    m, n := len(nums1), len(nums2)
7
    left, right := 0, m
8
    totalLeft := (m + n + 1)/2
9

10
    for left <= right {
11
        i := left + (right - left)/2
12
        j := totalLeft - i
13

14
        nums1LeftMax := math.MinInt
15
        if i > 0 {
16
            nums1LeftMax = nums1[i-1]
17
        }
18

19
        nums1RightMin := math.MaxInt
20
        if i < m {
21
            nums1RightMin = nums1[i]
22
        }
23

24
        nums2LeftMax  := math.MinInt
25
        if j > 0 {
26
            nums2LeftMax = nums2[j-1]
27
        }
28

29
        nums2RightMin := math.MaxInt
30
        if j < n {
31
            nums2RightMin = nums2[j]
32
        }
33

34
        if nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin {
35
            if (n + m) % 2 == 1 {
36
                return float64(max(nums1LeftMax, nums2LeftMax))
37
            }else {
38
                return float64(max(nums1LeftMax, nums2LeftMax) + min(nums1RightMin,nums2RightMin)) / 2.0
39
            }
40
        }else if nums1LeftMax > nums2RightMin {
41
            right = i - 1
42
        }else {
43
            left = i + 1
44
        }
45
    }
46
    return 0.0
47
}