4. Median of Two Sorted Arrays

Leetcode 链接

题目

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

题意解析

题目给出两个各自排序好的数组，求这两个数组组合后的中位数是什么？

解决方案一

对两个数组进行合并，然后排序，接着找出中位数即可。这样的好处是思路简单，但是开辟了新的空间。

Go 代码一

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    nums1 = append(nums1, nums2...)

    sort.Ints(nums1)

    mid := len(nums1) / 2
    if len(nums1) % 2 == 0 {
        return float64(nums1[mid-1] + nums1[mid]) / 2.0
    } else {
        return float64(nums1[mid])
    }
}

解决方案二

不需要开辟新的空间。对 nums1 和 nums2 同时进行遍历计数，根据已经遍历的数目就可以判断是否已经找到了中位数。

Go 代码二

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    var (
        odd        bool
        count, mid int
        res        float64
        len1       = len(nums1)
        len2       = len(nums2)
    )

    if (len1+len2)%2 != 0 {
        odd = true
        mid = (len1+len2)/2 + 1
    } else {
        mid = (len1 + len2) / 2
    }

    for i, j := 0, 0; i < len1 || j < len2; {
        t := 0
        if j >= len2 || (i < len1 && j < len2 && nums1[i] <= nums2[j]) {
            t = nums1[i]
            i++
        } else if i >= len1 || (i < len1 && j < len2 && nums1[i] > nums2[j]) {
            t = nums2[j]
            j++
        }

        count++

        switch count {
        case mid:
            res += float64(t)
            if odd {
                return res
            }
        case mid + 1:
            res += float64(t)
            return res / 2
        }
    }

    return res
}