为了更好的明天,坚持刷 LeetCode

题目

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

示例 1:

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

示例 2:

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

示例 3:

输入:nums1 = [0,0], nums2 = [0,0]
输出:0.00000

示例 4:

输入:nums1 = [], nums2 = [1]
输出:1.00000

示例 5:

输入:nums1 = [2], nums2 = []
输出:2.00000

提示:

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

解法一 - 合并数组

解题思路

暴力解法就是合并两个数组然后再找出中位数。

代码

func findMedianSortedArrays(nums1, nums2 []int) float64 {
    m, n := len(nums1), len(nums2)
    nums := make([]int, m + n)
    var i, j int
    for k := 0; k < len(nums); k++ {
        if i < m && j < n {
            if nums1[i] < nums2[j] {
                nums[k] = nums1[i]
                i++ 
            }else {
                nums[k] = nums2[j]
                j++
            }
        }else if i < m {
            nums[k] = nums1[i]
            i++
        }else if j < n {
            nums[k] = nums2[j]
            j++
        }
    }

    if len(nums) % 2 == 0 {
        return float64(nums[len(nums)/2] + nums[len(nums)/2-1])/2
    }
    return float64(nums[len(nums)/2])
}

执行结果

执行用时:16 ms,在所有 Go 提交中击败了 76.44% 的用户
内存消耗:5.7 MB,在所有 Go 提交中击败了 33.51% 的用户

复杂度分析

  • 时间复杂度:$O(m+n)$
  • 空间复杂度:$O(m+n)$

题目链接

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