LeetCode 第四题:寻找两个正序数组的中位数 【4/1000 】【python + go】

2024-04-03 20:12

本文主要是介绍LeetCode 第四题:寻找两个正序数组的中位数 【4/1000 】【python + go】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

👤作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。
会一些的技术:数据分析、算法、SQL、大数据相关、python
作者专栏每日更新:
LeetCode解锁1000题:打怪升级之旅
python数据分析可视化:企业实战案例
备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

题库中的“寻找两个正序数组的中位数”问题是一个经典的算法挑战。这个问题不仅出现在在线编程平台上,也是许多技术面试中的常见题目,值得深入探讨一下

问题描述

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

输入:nums1 = [1,3], nums2 = [2]
输出:2.0
解释:合并数组 = [1,2,3],中位数 2

解题思路

理解这个问题的关键在于,两个数组是有序的,这为我们提供了很多可以利用的性质。一种直观的解法是将两个数组合并成一个大的有序数组,然后直接找到中位数。虽然这种方法很直接,但它的时间复杂度为 (O(m+n)),并不是最优解。

最优解法 —— 二分查找法

要提高效率,可以考虑二分查找法。核心思路是,中位数将一个集合分为两个长度相等的子集,一个子集中的所有元素都小于另一个子集中的元素。对于两个有序数组,我们可以利用二分查找在 (O(\log(m+n))) 的时间复杂度内找到中位数。

算法步骤

确定较短的数组:为了减少查找的范围,我们总是在两个数组中较短的那个进行二分查找。
二分查找:在较短数组中进行二分查找,确定一个切点,使得两个数组被分为左右两个部分,左边部分的元素总数等于右边部分(或者多一个,如果总元素数为奇数)。
调整切点:通过比较两个数组在切点附近的元素,调整切点的位置,直到满足中位数的性质:左边部分的最大元素小于或等于右边部分的最小元素。
计算中位数:根据切点确定的左右两部分,计算中位数。

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 ("fmt""math"
)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, (m+n+1)/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 (m+n)%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(maxOfLeft+minOfRight) / 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 函数来简化代码,同时保持了算法的核心逻辑清晰明了。

这篇关于LeetCode 第四题:寻找两个正序数组的中位数 【4/1000 】【python + go】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/873866

相关文章

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1

python获取网页表格的多种方法汇总

《python获取网页表格的多种方法汇总》我们在网页上看到很多的表格,如果要获取里面的数据或者转化成其他格式,就需要将表格获取下来并进行整理,在Python中,获取网页表格的方法有多种,下面就跟随小编... 目录1. 使用Pandas的read_html2. 使用BeautifulSoup和pandas3.

Python装饰器之类装饰器详解

《Python装饰器之类装饰器详解》本文将详细介绍Python中类装饰器的概念、使用方法以及应用场景,并通过一个综合详细的例子展示如何使用类装饰器,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录1. 引言2. 装饰器的基本概念2.1. 函数装饰器复习2.2 类装饰器的定义和使用3. 类装饰

Python 交互式可视化的利器Bokeh的使用

《Python交互式可视化的利器Bokeh的使用》Bokeh是一个专注于Web端交互式数据可视化的Python库,本文主要介绍了Python交互式可视化的利器Bokeh的使用,具有一定的参考价值,感... 目录1. Bokeh 简介1.1 为什么选择 Bokeh1.2 安装与环境配置2. Bokeh 基础2

pandas中位数填充空值的实现示例

《pandas中位数填充空值的实现示例》中位数填充是一种简单而有效的方法,用于填充数据集中缺失的值,本文就来介绍一下pandas中位数填充空值的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录什么是中位数填充?为什么选择中位数填充?示例数据结果分析完整代码总结在数据分析和机器学习过程中,处理缺失数

如何使用 Python 读取 Excel 数据

《如何使用Python读取Excel数据》:本文主要介绍使用Python读取Excel数据的详细教程,通过pandas和openpyxl,你可以轻松读取Excel文件,并进行各种数据处理操... 目录使用 python 读取 Excel 数据的详细教程1. 安装必要的依赖2. 读取 Excel 文件3. 读

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服

Python的time模块一些常用功能(各种与时间相关的函数)

《Python的time模块一些常用功能(各种与时间相关的函数)》Python的time模块提供了各种与时间相关的函数,包括获取当前时间、处理时间间隔、执行时间测量等,:本文主要介绍Python的... 目录1. 获取当前时间2. 时间格式化3. 延时执行4. 时间戳运算5. 计算代码执行时间6. 转换为指

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技