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