leetcode4中位数

leecode

题目描述

给定两个大小分别为 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

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/median-of-two-sorted-arrays 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

法1

组合排序法

1. 用append函数组合两个数组

var a []int
 a = append(a, nums1...)//组合数组
 a = append(a, nums2...)

2. 使用sort.Ints函数对a数组进行排序

sort.Ints(a)//排序

3. 找中位数当为奇数时,就是a中间的数,为偶数时,就是中间两个数

if len(a)%2 == 0 {//偶数时
  return (float64(a[len(a)/2]) + float64(a[len(a)/2-1])) / 2
 } else {奇数时
  return float64(a[len(a)/2])
 }

执行结果

法1

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
 var a []int
 a = append(a, nums1...)
 a = append(a, nums2...)
 sort.Ints(a)
 if len(a)%2 == 0 {
  return (float64(a[len(a)/2]) + float64(a[len(a)/2-1])) / 2
 } else {
  return float64(a[len(a)/2])
 }
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 12 ms , 在所有 Go 提交中击败了 70.21% 的用户 内存消耗： 5.9 MB , 在所有 Go 提交中击败了 11.74% 的用户 通过测试用例： 2094 / 2094

法2