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

news/2024/6/16 10:15:54/文章来源:https://blog.csdn.net/CCIEHL/article/details/137253819

👤作者介绍: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 函数来简化代码,同时保持了算法的核心逻辑清晰明了。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1034818.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

31-5 命令执行漏洞 - RCE漏洞利用

环境准备:构建完善的安全渗透测试环境:推荐工具、资源和下载链接_渗透测试靶机下载-CSDN博客 一、打开pikachu靶场 二、远程命令执行利用 正常情况下这一关卡就是个ping命令,我们只能输入个 ip 靶场就就会ping 这ip 但是我们可以用管道符拼接来执行其他命令,详细可以看我…

Flutter 开发学习笔记(1):第一个简单的Flutter项目(上)

文章目录 前言相关链接初始化项目设置键盘映射建议使用AnLink链接物理机。 项目配置日志打印官方案例添加依赖主函数更换添加最简单的按钮Flutter 项目结构Flutter项目入口Flutter的MyApp函数 更新视图直接修改浅拷贝父节点数据思考 修改布局子节点重构子节点布局重构多次扩展布…

Github 2024-04-02Python开源项目日报 Top10

根据Github Trendings的统计,今日(2024-04-02统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Python项目10系统设计指南 创建周期:2507 天开发语言:Python协议类型:OtherStar数量:241693 个Fork数量:42010 次关注人数:241693 人贡献…

Intellij IDEA / Android studio 可持续开发笔记

Intellij 的Java/安卓工具链有着一种不可持续性&#xff0c;这种不可持续性体现在多个方面。 首先是不可持续运行。IDEA 使用时间越长&#xff0c;内存占用越大&#xff0c;从不主动释放。运行时间越长&#xff0c;日志越多&#xff0c;从不主动清理。 然后是不完整的开源&am…

【SQL Server】1. 认识+使用

1. 创建数据库的默认存储路径 C:\ProgramData\Microsoft\Windows\Start Menu\Programs\Microsoft SQL Server 2008 R2 当我们选择删除数据库时&#xff0c;对应路径下的文件也就删除了 2. 导入导出数据工具的路径 3. 注册数据库遇到的问题 ??? 目前的问题就是服务器新建…

【Qt】使用Qt实现Web服务器(九):EventSource+JSON实现工业界面数据刷新

1、效果 效果如下,实时刷新温度、湿度 2、源码 2.1 index.html <html><body> <!-- 页面布局,本人对HTML标签不熟悉,凑合看吧 --> <div><label for

Oracle基础-PL/SQL编程 备份

1、PL/SQL简介 PL/SQL块结构 约定&#xff1a;为了方便&#xff0c;本文后面把PL/SQL简称PL。 PL程序都是以块&#xff08;BLOCK&#xff09;为基本单位&#xff0c;整个PL块分三部分&#xff1a;声明部分&#xff08;使用DECLARE开头&#xff09;、执行部分(以BEGIN开头)和异…

【JavaEE初阶系列】——synchronized原理及优化(偏向锁,轻量级锁,自旋锁,锁消除,锁粗化)

目录 &#x1f6a9;synchronized锁特性详细解说 &#x1f6a9;加锁工作过程(锁升级) &#x1f388;偏向锁 &#x1f388;轻量级锁(自适应的自旋锁) &#x1f388; 重量级锁 &#x1f6a9;其他的优化操作 &#x1f388;锁消除 &#x1f388;锁粗化 &#x1f388;相关面…

JavaScript动态渲染页面爬取——Selenium的使用

JavaScript动态渲染页面爬取 JavaScript动态渲染得页面不止Ajax一种。例如&#xff0c;有些页面的分页部分由JavaScript生成&#xff0c;而非原始HTML代码&#xff0c;这其中并不包含Ajax请求。还有类似淘宝这种页面&#xff0c;即使是Ajax获取的数据&#xff0c;其Ajax接口中…

LeetCode题练习与总结:螺旋矩阵

一、题目描述 给你一个 m 行 n 列的矩阵 matrix &#xff0c;请按照 顺时针螺旋顺序 &#xff0c;返回矩阵中的所有元素。 示例 1&#xff1a; 输入&#xff1a;matrix [[1,2,3],[4,5,6],[7,8,9]] 输出&#xff1a;[1,2,3,6,9,8,7,4,5]示例 2&#xff1a; 输入&#xff1a;ma…

C#手术麻醉信息系统源码,技术框架:Vue,Ant-Design+百小僧开源框架

C#手术麻醉信息系统源码&#xff0c;技术框架&#xff1a;Vue&#xff0c;Ant-Design百小僧开源框架 手术麻醉系统主要用于在手术过程中监测和控制患者的状态&#xff0c;确保手术的顺利进行并保障患者的生命安全。该系统通过一系列先进的医疗设备和技术&#xff0c;为手术患者…

on-my-zsh 命令自动补全插件 zsh-autosuggestions 安装和配置

首先 Oh My Zsh 是什么? Oh My Zsh 是一款社区驱动的命令行工具&#xff0c;正如它的主页上说的&#xff0c;Oh My Zsh 是一种生活方式。它基于 zsh 命令行&#xff0c;提供了主题配置&#xff0c;插件机制&#xff0c;已经内置的便捷操作。给我们一种全新的方式使用命令行。…

Vue插槽(Slots)深入解析

插槽内容与出口​ 在之前的章节中&#xff0c;我们已经了解到组件能够接收任意类型的 JavaScript 值作为 props&#xff0c;但组件要如何接收模板内容呢&#xff1f;在某些场景中&#xff0c;我们可能想要为子组件传递一些模板片段&#xff0c;让子组件在它们的组件中渲染这些片…

蓝色wordpress外贸建站模板

蓝色wordpress外贸建站模板 https://www.mymoban.com/wordpress/7.html

【Hadoop大数据技术】——Hive数据仓库(学习笔记)

&#x1f4d6; 前言&#xff1a; Hive起源于Facebook&#xff0c;Facebook公司有着大量的日志数据&#xff0c;而Hadoop是实现了MapReduce模式开源的分布式并行计算的框架&#xff0c;可轻松处理大规模数据。然而MapReduce程序对熟悉Java语言的工程师来说容易开发&#xff0c;但…

Pycharm选择使用Anaconda环境中的Pytorch 失败解决办法之一

前几日想要复现一篇论文&#xff0c;结果给配的台式机完全禁不住&#xff0c;老是报溢出&#xff0c;慢都没事&#xff0c;溢出就很难受了&#xff0c;因此想用自己笔记本的GPU来训练。 安装以后遇到一个问题&#xff1a; Anaconda里创建了环境&#xff0c;安装好了对应pytor…

基于springboot的实习生管理系统

文章目录 项目介绍主要功能截图&#xff1a;部分代码展示设计总结项目获取方式 &#x1f345; 作者主页&#xff1a;超级无敌暴龙战士塔塔开 &#x1f345; 简介&#xff1a;Java领域优质创作者&#x1f3c6;、 简历模板、学习资料、面试题库【关注我&#xff0c;都给你】 &…

总结UDP协议各类知识点

前言 本篇博客博主将详细地介绍UDP有关知识点&#xff0c;坐好板凳发车啦~ 一.UDP特点 1.无连接 UDP传输的过程类似于发短信&#xff0c;知道对端的IP和端口号就直接进行传输&#xff0c;不需要建立连接&#xff1b; 2.不可靠传输 没有任何的安全机制&#xff0c;发送端发…

音视频基础 (九)---FFmpeg过滤器框架

ffmpeg的filter⽤起来是和Gstreamer的plugin是⼀样的概念&#xff0c;通过avfilter_link&#xff0c;将各个创建好的filter按 ⾃⼰想要的次序链接到⼀起&#xff0c;然后avfilter_graph_config之后&#xff0c;就可以正常使⽤。 ⽐较常⽤的滤镜有&#xff1a;scale、trim、over…

Golang Context是什么

一、这篇文章我们简要讨论Golang的Context有什么用 1、首先说一下Context的基本作用&#xff0c;然后在讨论他的实现 (1)数据传递&#xff0c;子Context只能看到自己的和父Context的数据&#xff0c;子Context是不能看到孙Context添加的数据。 (2)父子协程的协同&#xff0c;比…