求两个有序数组组合后的中位数(复杂度log(m+n))
叭叭一下如果某个cs门人焦虑了那那些学成男娘或秃头的人一定会说“什么你有时间焦虑”题目描述给定两个大小分别为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-106 nums1[i], nums2[i] 106分析要求求合并后的数组的中位数即使归并也需要mn复杂度复杂度要求log(mn)需要结合折半的思想才行最小k值法:转化为取第k小元素k为组合后长度一半 每次递归淘汰一半元素 最后得到第k小元素思路1最小k值法OK两数组长度m n那么中位数在(m n 1) / 2 和(m n 2) / 2位置奇数个两值相等偶数个为平均值那么怎么找到两个值首先取k分别为这两个值在两个数组中分别取k/2位置比较两个值对小的一个第k小元素肯定不在这个数组前k/2位置因为如果在这里的话假设为x这一半最多k/2个小于等于x另一个数组最多k/2-1个小于等于x这样最多k-1个小于等于x那x最多就是第k-1小的元素所以第k小元素不可能在这里。所以可以删去这k/2个元素既然已经删去了比第k小元素小的k/2个元素那问题转化为求剩下元素的第k-k/2小元素这样递归下去每次砍k/2的l次方元素直到k砍到为1直接取最小的那个就行了--这是一个递归退出条件。另一个递归退出条件是某个数组用尽直接在另一个数组取需要的值就行了。另外在比较的时候假如某个数组剩余长度小于当前k/2那就直接在另一个数组取要舍去的一半因为这一半已经不够舍去了(元素数小于k/2)所以另一个数组小于第k的元素一定多于k/2(否则总数不够k-1)。操作如下将问题转换为求两个有序数组合并后的第k小元素其中k (mn1)/2和k (mn2)/2处理奇偶。定义函数getKth(nums1, start1, nums2, start2, k)若其中一个数组已经用完直接返回另一个数组的当前第 k 个元素。若 k 1返回两个数组当前起始位置的最小值。否则比较两个数组的第k/2个元素若不够则取最后一个剔除较小元素所在数组的前 k/2 个元素递归查找剩余部分。最终中位数为两个k位置的平均值奇数时两次相同。时间复杂度每次递归减少 k/2递归深度 log(mn)满足要求。代码如下class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m nums1.length; int n nums2.length; int left (m n 1) / 2; int right (m n 2) / 2; return (getKth(nums1, 0, nums2, 0, left) getKth(nums1, 0, nums2, 0, right)) / 2.0; } public double getKth(int[] nums1, int start1, int[] nums2, int start2, int k) { if(start1 nums1.length) return nums2[start2 k - 1]; if(start2 nums2.length) return nums1[start1 k - 1]; if(k 1) return Math.min(nums1[start1], nums2[start2]); int mid1 (start1 k / 2 - 1 nums1.length) ? nums1[start1 k / 2 - 1] : Integer.MAX_VALUE; int mid2 (start2 k / 2 - 1 nums2.length) ? nums2[start2 k / 2 - 1] : Integer.MAX_VALUE; if(mid1 mid2) { return getKth(nums1, start1 k / 2, nums2, start2, k - k / 2); } else { return getKth(nums1, start1, nums2, start2 k / 2, k - k / 2); } } }另外附上我的个人网站作分享交流大圣的技术空间 - 沉心砺骨 向阳而生

相关新闻

金融工程Financial Engineering Competition-1回归MSE优化

金融工程Financial Engineering Competition-1回归MSE优化

回归分析是金融建模的基础工具之一,承担着预测变量值并量化误差的重要职责。本次金融工程竞赛围绕结构化数据中的数值关系展开,为学习者提供了一个全面接触特征处理与误差优化流程的实践平台。 本文围绕该任务进行系统解析,涵盖数据结构理解、回归建模思路、多模型对比、以…

2026/11/13 21:17:19 阅读更多 →
金融工程Financial Engineering Competition-2回归MSE优化

金融工程Financial Engineering Competition-2回归MSE优化

结构化数据建模在遇到特征缺失时仍需保持准确预测能力,是现代数据科学应用的重要挑战方向。通过在标准回归任务中引入信息缺失的设定,有助于训练算法处理现实中不完美输入的能力,尤其是在金融数据预测等典型场景下意义显著。 本文将围绕 Financial Engineering Competition…

2026/11/21 9:35:02 阅读更多 →
端云双模智能体完整方案:100M 端侧小模型 + L1-L5 五层人格记忆知识库 + GEF 灰度演化制衡体系

端云双模智能体完整方案:100M 端侧小模型 + L1-L5 五层人格记忆知识库 + GEF 灰度演化制衡体系

摘要 本文提出一套面向端侧资源受限场景的智能体架构方案,核心思路是「模型权重、人格记忆、大容量书库」三者彻底物理解耦。端侧以 100M 量级轻量 SLM 小模型承担工具任务,不固化人格与知识;L1-L4 人格记忆分层(本能内核、观念内…

2026/11/19 18:33:56 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/20 23:27:28 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/20 23:27:28 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/20 23:27:28 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/20 21:55:32 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/20 23:27:28 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/20 22:59:12 阅读更多 →

日新闻

周新闻

月新闻