Alomerry Wu @ alomerry.com

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

Jul 22, 2020 · 1min · 271 ·

Description

Difficulty: 困难

Related Topics: 数组, 二分查找, 分治

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

算法的时间复杂度应该为 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

Solution

要取得中位数,只需要将两条数组合并并排序,如果数组长度为偶数,则去中间两个取平均值,否则去中间的数即可。

@IOI/4.go

冒泡排序

algorithm/code/base/sort/bubble_sort.go

选择排序

algorithm/code/base/sort/select_sort.go)

插入排序

algorithm/code/base/sort/insert_sort.go)

归并排序

algorithm/code/base/sort/merge_sort.go)

堆排序

algorithm/code/base/sort/heap_sort.go)

快速排序

algorithm/code/base/sort/quick_sort.go)

 
 comment..
你认为这篇文章怎么样?
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v3.0.1
Theme by antfu
2018 - Present © Alomerry Wu