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

发表于 2019-07-04

| 0

| 阅读次数:

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。

示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0

示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5

通过 i 划分 nums1 为左右两部分 nums1[0], nums1[1], ..., nums1[i-1] 和 nums1[i], nums1[i+1], ..., nums1[m-1]
通过 j 划分 nums2 为左右两部分 nums2[0], nums2[1], ..., nums2[j-1] 和 nums2[j], nums2[j+1], ..., nums2[n-1]
如果 i, j 取值满足条件 i + j = m - i + n - j 和 nums1[i-1] < nums2[j], nums2[j-1] < nums1[i]（说明划分出了长度相等的左右两部分，并且左边的值都小于右边的值）
两个有序数组的中位数 (max(nums1[i-1], nums2[j-1]) + min(nums1[i], nums2[j])) / 2

示例代码(go)

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    m, n := len(nums1), len(nums2)
    if m > n {
        nums1, nums2 = nums2, nums1
        m, n = n, m
    }
    left, right, half := 0, m, (m + n + 1) / 2
    for left <= right {
        i := (left + right) / 2
        j := half - i
        if i < right && nums1[i] < nums2[j-1] {
            left = i + 1
        } else if i > left && nums1[i-1] > nums2[j] {
            right = i - 1
        } else {
            maxLeft, minRight := 0, 0
            if i == 0 {
                maxLeft = nums2[j-1]
            } else if j == 0 {
                maxLeft = nums1[i-1]
            } else {
                maxLeft = max(nums1[i-1], nums2[j-1])
            }
            if (m + n) % 2 == 1 {
                return float64(maxLeft)
            }
            if i == m {
                minRight = nums2[j]
            } else if j == n {
                minRight = nums1[i]
            } else {
                minRight = min(nums1[i], nums2[j])
            }
            return float64(maxLeft + minRight) / 2
        }
    }
    return 0.0
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}