windows10前段网站建设,wordpress 文章统计,美工招聘平台,南通网站制作维护. - 力扣#xff08;LeetCode#xff09;
题目
给定两个大小分别为 m 和 n 的正序#xff08;从小到大#xff09;数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (mn)) 。
示例 1#xff1a; 输入#xff1a;nums1 …. - 力扣LeetCode
题目
给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (mn)) 。
示例 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
提示
nums1.length mnums2.length n0 m 10000 n 10001 m n 2000
解题方案 首先明确中位数的位置 1. 暴力解法合并数组 合并成一个新数组然后sort取中位数。 边界情况合并后数组的长度为0则无中位数合并数组(nums)长度为偶数(n)则中位数为第位和第位的平均值即合并数组(nums)长度为奇数(n) 则中位数为第位即 接下来人生苦短我用Python~ class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) - float:# 合并数组并排序nums1.extend(nums2)nums1.sort()length len(nums1)if length 1:return Noneif length % 2 0:return (nums1[length // 2 - 1] nums1[length // 2]) / 2else:return nums1[length // 2]
分析时空复杂度
记nums1长度为m, nums2长度为n合并数组时间复杂度是空间复杂度是数组排序时间复杂度是空间复杂度是
故总的时间复杂度是空间复杂度是
虽然看上去代码非常精炼但是从时空复杂度上看算法并不好毕竟题目中正序从小到大数组这个条件没有用到。因此考虑有序归并
2. 暴力解法优化版有序合并数组
class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) - float:m len(nums1)n len(nums2)# 合并数组nums []if m 0:nums nums2elif n 0:nums nums1else:index_1 0index_2 0while True:if index_1 m and index_2 n:breakelif index_2 n or (index_1 m and nums1[index_1] nums2[index_2]):nums.append(nums1[index_1])index_1 1elif index_1 m or (index_2 n and nums1[index_1] nums2[index_2]):nums.append(nums2[index_2])index_2 1total_length len(nums)if total_length 1:return Noneelif total_length % 2 0:return (nums[total_length // 2 - 1] nums[total_length // 2]) / 2else:return nums[total_length // 2]
分析时空复杂度
时间复杂度为合并数组花费的时间空间复杂度为合并后数组的空间 如果不存储合并的数组空间复杂度可以做到O(1)
题目给出的条件都用上了时空复杂度也得到了提升但仍然不符合题目要求的 O(log (mn))的时间复杂度需要进一步优化。
有序数组寻找中位数考虑二分法。
3. 二分法 考虑一个长度为n有序数组的中位数其中位数 如果n为奇数则中位数为第大的数。如果n为偶数则中位数为第大的数和第大的数的平均值。 因此中位数问题可以转换为另一个问题寻找数组中第k小的数 对于长度为偶数的情况需要寻找两次并取平均值 class Solution:def getKthNumber(self, nums1: List[int], nums2: List[int], k: int) - int:寻找两个正序整数数组中第k小的数passdef findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) - float:中位数计算入口函数total_length len(num1) len(nums2)if total_length 1:return Noneelif total_length % 2 0:return (self.getKthNumber(nums1, nums2, total_length // 2) self.getKthNumber(nums1, nums2, total_length // 2 1)) / 2else:return self.getKthNumber(num1, nums2, total_length // 2 1) 接着看如何寻找两个正序数组中第k小的数 如果时间复杂度是O(log (mn))考虑用二分法。 先看下面这个例子 由此我们可以总结我们两个正序数组中寻找第k小的数的思路 1. 如果k1, 则首先比较两个数组首位元素取最小的一个。 2. 如果k1, 则比较两个数组中第个元素较小的一个数组中的第1~个元素一定是小于我们目标值的因此可以排除这一段如上图中灰色部分在剩余元素中继续寻找第()小的元素。 3. 如果某个数组完全被排除掉了则直接在剩余的另一个数组中定位目标元素即可。如下面的例子 class Solution:def getKthNumber(self, nums1: List[int], nums2: List[int], k: int) - int:寻找两个正序整数数组中第k大的数# 记录数组长度m len(nums1)n len(nums2)# 记录数组可以查找的起始位置索引index_1 0index_2 0while True:# 极端情况1 - nums1已经被排除为空if index_1 m:return nums2[index_2 k - 1]# 极端情况2 - nums2已经被排除为空if index_2 n:return nums1[index_1 k - 1]# 极端情况3 - 寻找最小的数if k 1:return min(nums1[index_1], nums2[index_2])# 正常情况, 二分查找new_index_1 min(k // 2 - 1 index_1, m - 1)new_index_2 min(k // 2 - 1 index_2, n - 1)if nums1[new_index_1] nums2[new_index_2]:k - (new_index_1 - index_1 1)index_1 new_index_1 1else:k - (new_index_2 - index_2 1)index_2 new_index_2 1def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) - float:寻找中位数 入口函数total_length len(nums1) len(nums2)if total_length 1:return Noneelif total_length % 2 0:return (self.getKthNumber(nums1, nums2, total_length // 2) self.getKthNumber(nums1, nums2, total_length // 2 1)) / 2else:return self.getKthNumber(nums1, nums2, total_length // 2 1)
分析时空复杂度 时间复杂度 空间复杂度
AI会怎么做
智谱清言给出了一种更高效的解法划分数组二分法。 思路 对一个长度为n的数组从任意位置i将数组划分为两部分可以有n1种分发如图所示4个元素的数组有415种划分方法。 中位数的作用是什么呢将一个集合划分为两个长度相等的子集其中一个子集中的元素总是大于另一个子集中的元素。 对数组A从i位置进行划分对数组B在j位置划分数组A的左半部分和数组B的左半部分合起来叫做left_part, 数组A的有半部分和数组B的右半部分合起来叫做right_part 则中位数是这样的一种划分 对于两个数组长度之和为偶数的情况中位数为,此时划分位置满足对于两个数组长度之和为奇数的情况中位数为此时划分位置满足合并上述两种可以知道中位数情况下的划分如果我们保证(避免j计算出负数) 可以导出通过上述推导中位数问题可以转换为寻找使得且其中进一步简化为在中寻找最大的使得,其中。接下来就可以在上对进行二分查找了。 如此复杂的推导过程又是担心被AI取代的一天。。。
def findMedianSortedArrays(nums1, nums2):# 确保 nums1 是较短的数组if len(nums1) len(nums2):nums1, nums2 nums2, nums1m, n len(nums1), len(nums2)imin, imax, half_len 0, m, (m n 1) // 2while imin imax:i (imin imax) // 2j half_len - iif i m and nums1[i] nums2[j - 1]:# i 需要增大imin i 1elif i 0 and nums1[i - 1] nums2[j]:# i 需要减小imax i - 1else:# 找到合适的 i 和 jmax_of_left 0if i 0: max_of_left nums2[j - 1]elif j 0: max_of_left nums1[i - 1]else: max_of_left max(nums1[i - 1], nums2[j - 1])if (m n) % 2 1:return max_of_leftmin_of_right 0if i m: min_of_right nums2[j]elif j n: min_of_right nums1[i]else: min_of_right min(nums1[i], nums2[j])return (max_of_left min_of_right) / 2.0# 示例
print(findMedianSortedArrays([1, 3], [2])) # 输出: 2.0
print(findMedianSortedArrays([1, 2], [3, 4])) # 输出: 2.5
