LeetCode - 寻找两个正序数组的中位数

题目

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

示例 5:

1
2
输入: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

进阶:你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗?

解题

方法

方法1:最直观的方法【时间复杂度不符合】

看到题目,最直观的方法就是合并两个数组,并且取合并后的数组的中位数(奇数和偶数中位数不一样)。

时间复杂度:遍历全部数组 O(m+n),很明显和题目不符,题目需要的是 O(log (m+n))

空间复杂度:开辟了一个数组,保存合并后的两个数组 O(m+n)

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
type IntSlice []int

func (s IntSlice) Len() int {
return len(s)
}

func (s IntSlice) Less(i, j int) bool {
return s[i] < s[j]
}

func (s IntSlice) Swap(i, j int) {
s[i], s[j] = s[j], s[i]
}

// 寻找两个正序数组的中位数
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
if len(nums1) == 0 && len(nums2) == 0 {
return 0
}
arr := append(nums1, nums2...)
s := IntSlice(arr)
sort.Sort(s)
if len(s)%2 == 1 {
return float64(s[(len(s)+1)/2-1])
}
return (float64(s[(len(s)-2)/2]) + float64(s[(len(s)+2)/2-1])) / 2
}

方法2:二分法

题目中要求的时间复杂度是 O(log (m+n)),这个复杂度往往都需要结合 二分法 来处理,

方法3:看不懂的方法

这个方法看不懂,比较有挑战性,有兴趣的话可以自己去尝试下,方法在这:看不懂的方法

单元测试

测试结果

总结

本文作者:Jormin
本文地址https://blog.lerzen.com/leetcode-寻找两个正序数组的中位数/
版权声明:本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 CN 许可协议。转载请注明出处!

----- 到这结束咯 感谢您的阅读 -----