算法题3 #3/5(未完)

保持思考的习惯

转载自leetcode,题目描述:

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

难度困难3767

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


示例 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

示例 3:

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

示例 4:

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

示例 5:

输入:nums1 = [2], nums2 = []输出:2.00000



拿到之后第一眼的思路:

先合并两个列表为一个列表,然后分两种情况:

case1.列表长度为偶数,为偶数的话,中位数就是最中间两位数加起来除以2(下标分别为n/2 - 1 and n/2)

case2.列表长度为奇数的话,中位数就是最中间的那个数,下标n-1/2(这个好实现)



待续。。官方讲解的二分法没太看懂,困了,明日继续

3/7继续更

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/shuang-zhi-zhen-by-powcai/

先码一个在这里,这个答案看了一遍云里雾里的,哭鸟

这道题虽然用我上面的简单方法能够写出来,但是还涉及到了关于时间复杂度的讨论,🔺这里我不是很能够理解。可以在CB老师的python算法课上解决这个理解问题

= =

看不懂啊,这道题先放放,难度降级难度降级

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容