题目描述
给定两个大小分别为 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
解题思路
这道题很简单，不管是题目说明还是提示都给出了我们解题思路。
- 首先我们需要把给定的两个有序数组进行合并
- 分两种情况来求出中位数：
2.1 一种情况是长度是偶数，则中位数是中间两个数之和再除以2得到中位数；
2.2 另一种情况是合并后的数组长度是奇数，则最中间的元素就是我们要找到的中位数。
AC代码
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { len1 := len(nums1) len2 := len(nums2) lenSum := len1+len2 if lenSum == 0 { return float64(0) } l, r := 0, 0 a := make([]int,0,lenSum) for l <len1 && r < len2{ if nums1[l] < nums2[r]{ a = append(a,nums1[l]) l++ }else { a = append(a, nums2[r]) r++ } } a = append(a, nums1[l:]...) a = append(a, nums2[r:]...) if lenSum%2 != 0 { return float64(a[lenSum/2]) }else { return (float64(a[lenSum/2-1]) + float64(a[lenSum/2]))/2 } }
运行结果
