4. 两个有序数组的中位数

给定两个有序数组 nums1 和 nums2，它们的大小分别是 m 和 n，返回它们合并后的数组的中位数。

算法的复杂度须为 。

例一：

输入: nums1 = [1,3], nums2 = [2]
输出: 2.00000
解释: 两数组合并后得到数组 [1,2,3]，其中位数为 2。

例二：

输入: nums1 = [1,2], nums2 = [3,4]
输出: 2.50000
解释: 两数组合并后得到数组 [1,2,3,4]，其中位数为 (2 + 3) / 2 = 2.5.

条件：

• 两数组的长度分别为 m 和 n；
• 两数组的最大长度为 1000，最小长度为 0。
• 合并后的数组长度最小为 1，最大为 2000。
• 数组中的值范围为 [-10^6, 10^]。

解题思路：二分查找

由于题目中的条件是有序数组，因此，很容易想到可以用二分查找，这里，对两数组中长度较小的数组做二分是为了减少时间复杂度，其原因在于如果一个数组的索引 确定了，那么另一个数组的索引位置 也就确定了，因为 和 相加等于 ( m 加 n 的结果为奇数)，其中 m 、n 分别是两数组的长度。

具体的实现如下：

func findMedianSortedArrays(nums1, nums2 []int) float64 {
    Infinity := 100000000000 // 范围
    if len(nums1) > len(nums2) {
        nums1, nums2 = nums2, nums1 // 无论合适，确保 nums1 为小数组，nums2 为大数组
    }
    len1, len2 := len(nums1), len(nums2)
    low := 0
    high := len1
    for low <= high {
        i := low + (high-low)/2 //
        j := (len1+len2+1)/2 - i

        maxLeftNums1, minRightNums1, maxLeftNums2, minRightNums2 := 0, 0, 0, 0
        if i == 0 {
            maxLeftNums1 = -Infinity
        } else {
            maxLeftNums1 = nums1[i-1]
        }

        if i == len1 {
            minRightNums1 = Infinity
        } else {
            minRightNums1 = nums1[i]
        }

        if j == 0 {
            maxLeftNums2 = -Infinity
        } else {
            maxLeftNums2 = nums2[j-1]
        }

        if j == len2 {
            minRightNums2 = Infinity
        } else {
            minRightNums2 = nums2[j]
        }

        if (maxLeftNums1 <= minRightNums2) && (minRightNums1 >= maxLeftNums2) {
            if (len1+len2)%2 == 1 {
                return float64(max(maxLeftNums1, maxLeftNums2))
            }
            return float64(max(maxLeftNums1, maxLeftNums2)+min(minRightNums1, minRightNums2)) / 2
        } else if maxLeftNums1 > minRightNums2 {
            high = i - 1
        } else {
            low++
        }
    }
    return 0
}

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

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

Runtime: 10 ms, faster than 88.38% of Go online submissions for Median of Two Sorted Arrays.
Memory Usage: 5 MB, less than 90.27% of Go online submissions for Median of Two Sorted Arrays.

还有两种参考的实现方式：

方法一

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    sum := len(nums1) + len(nums2)
    if sum%2 == 1 {
        return float64(getDivLine(nums1, nums2, sum/2+1))
    }
    return float64(getDivLine(nums1, nums2, sum/2+1)+getDivLine(nums1, nums2, sum/2)) / 2.0

}

func getDivLine(nums1, nums2 []int, need int) int {
    index1, index2 := 0, 0
    for {
        if index1 == len(nums1) {
            return nums2[index2+need-1]
        }
        if index2 == len(nums2) {
            return nums1[index1+need-1]
        }
        if need == 1 {
            return min(nums1[index1], nums2[index2])
        }
        half := need / 2
        newIndex1 := min(index1+half, len(nums1)) - 1
        newIndex2 := min(index2+half, len(nums2)) - 1
        pivot1, pivot2 := nums1[newIndex1], nums2[newIndex2]
        if pivot1 <= pivot2 {
            need -= newIndex1 - index1 + 1
            index1 = newIndex1 + 1
        } else {
            need -= newIndex2 - index2 + 1
            index2 = newIndex2 + 1
        }
    }
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

结果：

Runtime: 19 ms, faster than 47.55% of Go online submissions for Median of Two Sorted Arrays.
Memory Usage: 5.1 MB, less than 81.02% of Go online submissions for Median of Two Sorted Arrays.

方法二

func findMedianSortedArrays2(nums1 []int, nums2 []int) float64 {
    m, n := len(nums1), len(nums2)
    if (m+n)%2 == 0 {
        val1 := findKth(nums1, nums2, (m+n)/2)
        val2 := findKth(nums1, nums2, (m+n)/2+1)
        return (float64(val1) + float64(val2)) * 0.5
    } else {
        val := findKth(nums1, nums2, (m+n+1)/2)
        return float64(val)
    }
}

func findKth(nums1 []int, nums2 []int, k int) int {
    if len(nums1) == 0 {
        return nums2[k-1]
    }
    if len(nums2) == 0 {
        return nums1[k-1]
    }
    if len(nums1) > len(nums2) {
        return findKth(nums2, nums1, k)
    }
    if k == 1 {
        if nums1[0] < nums2[0] {
            return nums1[0]
        } else {
            return nums2[0]
        }
    }
    mi := k >> 1
    mi1, mi2 := mi-1, mi-1
    if mi1 >= len(nums1) {
        mi1 = len(nums1) - 1
    }
    if nums1[mi1] <= nums2[mi2] {
        nums1 := nums1[mi1+1:]
        k = k - (mi1 + 1)
        return findKth(nums1, nums2, k)
    } else {
        nums2 := nums2[mi2+1:]
        k = k - (mi2 + 1)
        return findKth(nums1, nums2, k)
    }
}

结果：

Runtime: 26 ms, faster than 22.48% of Go online submissions for Median of Two Sorted Arrays.
Memory Usage: 5.1 MB, less than 81.02% of Go online submissions for Median of Two Sorted Arrays.

附

下一题传送门