每天一道LeetCode算法题-寻找两个有序数组的中位数
每天一道LeetCode算法题,说是这么说,我这都间隔好几天了2333333。回归正题,看官们请看今天的题目描述:
题目描述
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例1
2
3
4
5
6
7nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
思考
要求算法的时间复杂度为 O(log(m + n))???,我终于知道为啥这题标的是困难了。我等咸鱼选择放弃,还是直接学习官方题解好了2333333~
题解
方法:递归法。
为了解决这个问题,我们需要理解“中位数的作用是什么”。在统计中,中位数被用来:
将一个集合划分为两个长度相等的子集,其中一个子集中的元素总是大于另一个子集中的元素。
首先,让我们在任一位置 i 将 A 划分成两个部分:1
2 left_A | right_A
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
由于 A 中有 m 个元素, 所以我们有 m+1 种划分的方法(i = 0 ∼ m)。
采用同样的方式,我们在任一位置 j 将 B 划分成两个部分:1
2 left_B | right_B
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
将 left_A 和 left_B 放入一个集合,并将 right_A 和 right_B 放入另一个集合。 再把这两个新的集合分别命名为 left_part 和 right_part:1
2
3 left_part | right_part
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
如果我们可以确认:1
2len(left_part) = len(right_part)
max(left_part) ≤ min(right_part)
那么,我们已经将 {\text{A}, \text{B}}{A,B} 中的所有元素划分为相同长度的两个部分,且其中一部分中的元素总是大于另一部分中的元素。那么:
median = (max(left_part) + min(right_part)) / 2
要确保这两个条件,我们只需要保证:
希望这篇文章能给你带来知识和乐趣,喜欢博主的文章可以加博主好友哦
有好的文章也可以向博主投稿哦
您的喜欢是作者写作最大的动力
QQ群和公众号