织梦企业网站,免备案主机,注册公司的流程及手续,dede网站 远程生成 #x1f464;作者介绍#xff1a;10年大厂数据\经营分析经验#xff0c;现任大厂数据部门负责人。 会一些的技术#xff1a;数据分析、算法、SQL、大数据相关、python 作者专栏每日更新#xff1a; LeetCode解锁1000题:打怪升级之旅 python数据分析可视化:企业实战案例… 作者介绍10年大厂数据\经营分析经验现任大厂数据部门负责人。 会一些的技术数据分析、算法、SQL、大数据相关、python 作者专栏每日更新 LeetCode解锁1000题:打怪升级之旅 python数据分析可视化:企业实战案例 备注说明方便大家阅读统一使用python带必要注释公众号 数据分析螺丝钉 一起打怪升级 题库中的“寻找两个正序数组的中位数”问题是一个经典的算法挑战。这个问题不仅出现在在线编程平台上也是许多技术面试中的常见题目值得深入探讨一下
问题描述
给定两个大小分别为 m 和 n 的正序非递减数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。示例
输入nums1 [1,3], nums2 [2]
输出2.0
解释合并数组 [1,2,3]中位数 2解题思路
理解这个问题的关键在于两个数组是有序的这为我们提供了很多可以利用的性质。一种直观的解法是将两个数组合并成一个大的有序数组然后直接找到中位数。虽然这种方法很直接但它的时间复杂度为 (O(mn))并不是最优解。
最优解法 —— 二分查找法
要提高效率可以考虑二分查找法。核心思路是中位数将一个集合分为两个长度相等的子集一个子集中的所有元素都小于另一个子集中的元素。对于两个有序数组我们可以利用二分查找在 (O(\log(mn))) 的时间复杂度内找到中位数。
算法步骤
确定较短的数组为了减少查找的范围我们总是在两个数组中较短的那个进行二分查找。 二分查找:在较短数组中进行二分查找确定一个切点使得两个数组被分为左右两个部分左边部分的元素总数等于右边部分或者多一个如果总元素数为奇数。 调整切点:通过比较两个数组在切点附近的元素调整切点的位置直到满足中位数的性质左边部分的最大元素小于或等于右边部分的最小元素。 计算中位数:根据切点确定的左右两部分计算中位数。
python示例
def find_median_sorted_arrays(nums1: [int], nums2: [int]) - float:# 确保 nums1 是两个中较短的数组if len(nums1) len(nums2):nums1, nums2 nums2, nums1m, n len(nums1), len(nums2)# 初始化二分查找的边界left, right, half_len 0, m, (m n 1) // 2while left right:# i 和 j 分别为两个数组的切分点i (left right) // 2j half_len - i# 调整左边界if i m and nums2[j-1] nums1[i]:left i 1# 调整右边界elif i 0 and nums1[i-1] nums2[j]:right i - 1else:# 找到合适的切分点计算中位数if 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:# 如果 m n 是奇数中位数是左半部的最大值return max_of_left# 如果 m n 是偶数中位数是左半部的最大值和右半部的最小值的平均值if 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.0return 0# 示例测试
nums1 [1, 3]
nums2 [2]
print(f中位数是{find_median_sorted_arrays(nums1, nums2)})代码解读
让我们一步一步分析上面的Python代码以解释它是如何找到两个有序数组中位数的。
关键变量
nums1 和 nums2: 输入的两个有序数组。m 和 n: 分别是 nums1 和 nums2 的长度。left 和 right:用于在较短数组 nums1 上执行二分查找的指针。half_len: 两个数组合并后左半部分的长度。
二分查找
二分查找的目的是在较短的数组 nums1 中找到一个位置 i同时在 nums2 中找到位置 j使得
nums1[i-1] nums2[j] 且 nums2[j-1] nums1[I]
位置 i 和 j 的选取使得nums1和nums2被分割成两个部分左半部分的所有元素都不大于右半部分的元素。
边界条件处理
循环中的条件判断用于处理边界条件确保不会访问数组外的元素
如果 i 还可以增大并且 nums2[j-1] nums1[i]那么需要将 left 移动到 i 1这意味着 i 的位置太小需要向右移动以增大 i。如果 i 还可以减小并且 nums1[i-1] nums2[j]那么需要将 right 移动到 i - 1这意味着 i 的位置太大需要向左移动以减小 i。
计算中位数
一旦找到了合适的 i 和 j中位数可以通过下列方式计算
当 m n 为奇数时中位数是左半部分的最大值。当 m n 为偶数时中位数是左半部分的最大值和右半部分的最小值的平均值。 代码中使用了几个条件判断来处理这个逻辑确保即使在边界条件下比如某一数组的所有元素都在另一数组的左边或右边时也能正确计算中位数。
返回结果
最后根据 m n 的奇偶性返回合适的中位数值。
这个算法精妙地利用了二分查找和有序数组的性质来高效地解决问题避免了将两个数组合并后再查找中位数从而达到了更优的时间复杂度 O(log(min(m,n)))。
goland示例
我们同样可以采用二分查找法。以下是 Go 语言版本的实现及其解读。
package mainimport (fmtmath
)func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {// 确保 nums1 是较短的数组if len(nums1) len(nums2) {nums1, nums2 nums2, nums1}m, n : len(nums1), len(nums2)left, right, halfLen : 0, m, (mn1)/2var maxOfLeft, minOfRight intfor left right {i : (left right) / 2j : halfLen - iif i m nums2[j-1] nums1[i] {left i 1} else if i 0 nums1[i-1] nums2[j] {right i - 1} else {if i 0 {maxOfLeft nums2[j-1]} else if j 0 {maxOfLeft nums1[i-1]} else {maxOfLeft int(math.Max(float64(nums1[i-1]), float64(nums2[j-1])))}if (mn)%2 1 {return float64(maxOfLeft)}if i m {minOfRight nums2[j]} else if j n {minOfRight nums1[i]} else {minOfRight int(math.Min(float64(nums1[i]), float64(nums2[j])))}return float64(maxOfLeftminOfRight) / 2.0}}return 0.0
}func main() {nums1 : []int{1, 3}nums2 : []int{2}fmt.Println(中位数是, findMedianSortedArrays(nums1, nums2))
}代码解读
此解决方案首先检查 nums1 和 nums2 的长度确保 nums1 是较短的数组这样可以减少我们二分查找的范围。left 和 right 变量定义了 nums1 上的查找范围而 halfLen 变量则根据两数组的总长度计算中位数左侧的元素数量。在二分查找过程中i 和 j 分别表示 nums1 和 nums2 中用于分割数组的索引。left 和 right 的调整基于 nums1[i] 和 nums2[j] 的比较以确保左侧的最大值不大于右侧的最小值。当找到合适的分割线时根据奇偶性计算中位数。如果总长度是奇数则中位数是左侧的最大值如果是偶数则中位数是左侧最大值和右侧最小值的平均数。
总结
通过这种方法我们能够在 O(log(min(m,n))) 时间复杂度内找到两个有序数组的中位数。Go 语言的实现利用了数学库中的 math.Max 和 math.Min 函数来简化代码同时保持了算法的核心逻辑清晰明了。
