保持思考的习惯
转载自leetcode,题目描述:
难度困难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算法课上解决这个理解问题
= =
看不懂啊,这道题先放放,难度降级难度降级