LeetCode-热题100：4. 寻找两个正序数组的中位数

本文主要是介绍LeetCode-热题100：4. 寻找两个正序数组的中位数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

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

示例 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

提示：

• 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 []int, nums2 []int) float64 {var num []int  // 用于存储合并后的数组len1 := len(nums1)len2 := len(nums2)length := len1 + len2  // 合并后数组的长度// 将nums1和nums2合并到num数组中for i := 0; i < len1; i++ {num = append(num, nums1[i])}for j := len1; j < length; j++ {num = append(num, nums2[j - len1])}// 对合并后的数组进行排序sort.Ints(num)// 计算中位数if length%2 == 1 {return float64(num[length / 2])}mid1 := num[length / 2]    mid2 := num[length / 2 - 1]return float64(mid1 + mid2) / 2.0
}

代码解释

1. 初始化合并数组:

   • 定义一个新的切片 num 用于存储合并后的数组。

2. 合并两个数组:

   • 遍历 nums1，将其元素添加到 num 中。
   • 遍历 nums2，将其元素添加到 num 中。

3. 对合并后的数组进行排序:

   • 使用 sort.Ints(num) 对合并后的数组 num 进行排序。

4. 计算中位数:

   • 如果合并后的数组的长度 length 是奇数，直接返回中间的数值。
   • 如果 length 是偶数，计算中间两个数的平均值。

5. 返回结果:

   • 返回中位数。

时间复杂度分析：

• 合并数组和排序数组的时间复杂度是 O(m+n)，其中 m 和 n 分别是 nums1 和 nums2 的长度。
• 计算中位数的时间复杂度是 O(1)。

总的时间复杂度是 O(m+n)。

这篇关于LeetCode-热题100：4. 寻找两个正序数组的中位数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---