日拱一卒(9)——leetcode学习记录:两数组中位数

一、问题

给定两个大小分别为 mn 的排序数组 nums1nums2,要求你在 O(log(m+n)) 的时间复杂度内找出这两个数组的中位数。

二、思路

时间复杂度O(log(n))代表随着操作数增加,剩余操作数递减,如二分法。

首先要建模,对这个问题有一个具体的表达,建模的方式决定了解决问题的难易程度。在这里我就是因为错误建模走错了方向,需要分类讨论的情况越来越多,问题越来越复杂。

首先看到时间复杂度的要求,表明应该与二分法相关,如何把这个问题与二分挂钩呢。这个问题要找两个数组合并后的中位数,实际上,合并后数组的中位数就是将数组分成两半,中间的数就是中位数。换句话说要将这个数组分成两个大小相等的数组,其中一个数组中的最大元素小于另一个数组的最小元素,如下图所示。图片来自4. 寻找两个正序数组的中位数 - 力扣(LeetCode)

可见,问题的关键在于找到这样一个分割线,使得左侧的最大值小于右侧的最小值。

三、题解

class Solution:

    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:

        # 二分查找

        m = len(nums1)

        n = len(nums2)

        if m > n:

            nums1,nums2 = nums2,nums1

            m,n = len(nums1),len(nums2)

        # 从数组1中取line1个数,从数组2中取line2个数组成left,其余是right

        line1 = 0

        infinty = 2**40

        while line1 <= m:

            line2 = (m+n+1)//2 - line1

            maxleft1 = nums1[line1-1] if line1 > 0 else -infinty

            maxleft2 = nums2[line2-1] if line2 > 0 else -infinty

            maxleft = max(maxleft1,maxleft2)

            minright1 = nums1[line1] if line1 < m else infinty

            minright2 = nums2[line2] if line2 < n else infinty

            minright = min(minright1,minright2)

            if maxleft <= minright:

                return maxleft if (m+n)%2 == 1 else (maxleft+minright)/2

            else:

                line1 += 1

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

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

相关文章

从 HTML 到 CSS:开启网页样式之旅(五)—— CSS盒子模型

从 HTML 到 CSS&#xff1a;开启网页样式之旅&#xff08;五&#xff09;—— CSS盒子模型 前言一、盒子模型的组成margin&#xff08;外边距&#xff09;&#xff1a;border&#xff08;边框&#xff09;&#xff1a;padding&#xff08;内边距&#xff09;&#xff1a;conten…

【区块链】深入理解区块链中的 Gas 机制

&#x1f308;个人主页: 鑫宝Code &#x1f525;热门专栏: 闲话杂谈&#xff5c; 炫酷HTML | JavaScript基础 ​&#x1f4ab;个人格言: "如无必要&#xff0c;勿增实体" 文章目录 深入理解区块链中的 Gas 机制一、Gas 的基本概念1.1 为什么需要 Gas&#xff1f…

黑马JavaWeb-day06、07、08(SQL部分) _

文章目录 MYSQL概述数据模型SQL简介SQL分类 DDL数据库操作表操作 DML增&#xff08;INSERT&#xff09;改&#xff08;UPDATE&#xff09;删&#xff08;DELETE&#xff09; DQL基本查询条件查询&#xff08;where&#xff09;分组查询&#xff08;group by&#xff09;排序查询…

Kubernetes集群操作

查看集群信息&#xff1a; kubectl get nodes 删除节点 &#xff08;⽆效且显示的也可以删除&#xff09; 后期如果 要删除某个节点&#xff0c;为了不增加其他节点的访问压力&#xff0c;先增加一个节点&#xff0c;再删除要删除的节点 语法 &#xff1a;kubect delete…

基于PSO粒子群优化的CNN-LSTM-SAM网络时间序列回归预测算法matlab仿真

目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 5.算法完整程序工程 1.算法运行效果图预览 (完整程序运行后无水印) 2.算法运行软件版本 matlab2022a 3.部分核心程序 &#xff08;完整版代码包含详细中文注释和操作步骤视频&#xff09…

三步入门Log4J 的使用

本篇基于Maven 的Project项目&#xff0c; 快速演示Log4j 的导入和演示。 第一步&#xff1a; 导入Log4j依赖 <dependency><groupId>org.apache.logging.log4j</groupId><artifactId>log4j-api</artifactId><version>2.24.2</version&…

Redis 基础、Redis 应用

Redis 基础 什么是 Redis&#xff1f; Redis &#xff08;REmote DIctionary Server&#xff09;是一个基于 C 语言开发的开源 NoSQL 数据库&#xff08;BSD 许可&#xff09;。与传统数据库不同的是&#xff0c;Redis 的数据是保存在内存中的&#xff08;内存数据库&#xf…

3D数据大屏实现过程,使用echarts、Next.js

&#x1f4dc; 本文主要内容 数据大屏自适应方案动效 echarts&#xff1a; 3D 立体柱状图动态流光折线图 3D 地球&#xff08;飞线、柱状图&#xff09;无限滚动列表 &#x1f50d; 大屏效果 数据大屏&#xff1a; 点击预览 &#x1f579; 运行条件 next 12.3.4echarts 5.4…

标贝科技受邀出席2024东湖国际人工智能高峰论坛并入选数据要素合作伙伴名单

近日&#xff0c;备受瞩目的2024东湖国际人工智能高峰论坛在中国光谷科技会展中心隆重召开。会议以“智联世界&#xff0c;共创未来”为主题&#xff0c;省市相关单位、专家学者、产学研各界百余家联合体单位齐聚一堂&#xff0c;共话人工智能领域的最新技术及产业发展趋势。会…

unity与android拓展

一.AndroidStudio打包 1.通过Unity导出Android Studio能够打开的工程 步骤 1.设置导出基本信息&#xff1a;公司名、游戏名、图标、包名等关键信息 2.在File——>Build Settings中&#xff0c;勾选 Export Project 选项 3.点击Export 导出按钮 2.在Android Studio中打开Un…

linux通过fork()和execve()调用其他程序在子线程中运行

fork()的的使用见上一期 linux C fork()和系统调用文件-CSDN博客 简单说一下fork的作用就是创造一个子进程和当前进程一起执行下面的代码 pid_t fork(void) execve的作用为&#xff1a;让当前进程内容销毁大部分&#xff0c;重新执行一个程序 int execve (const char *__path…

整数benders分解算法

benders分解是将问题分为限制主问题和子问题&#xff0c;然后主问题向子问题传入变量&#xff0c;接着根据子问题求解的信息向主问题返回割&#xff08;最优割和可行割&#xff09;&#xff0c;这些割以约束的形式被添加到主问题中。其中&#xff0c;子问题因为求解得到的解是可…

Unity之(多语言)Localization本地化工具

一、安装和配置 Localization Localization是Unity基于对多种语言和区域变体所设计的一个本地化工具&#xff0c;常用与切换多国语言时文本、图片的动态替换。 1.安装Localization插件 Window—> Package Manager&#xff0c;打开Package Manager面板 Packages选择Unity Re…

使用Mac下载MySQL修改密码第一篇_数据库

Mac下载MySQL MySQL官网链接MySQL​​​​​​ 当进入到官网后下滑到community社区&#xff0c;进行下载 然后选择community sever下载 这里就是要下载的界面&#xff0c;如果需要下载之前版本的话可以点击archives&#xff0c; 可能会因为这是外网原因&#xff0c;有时候下…

服务器数据恢复—EVA存储硬盘磁头和盘片损坏离线的数据恢复案例

服务器存储数据恢复环境&故障&#xff1a; 一台HP EVA存储中有23块硬盘&#xff0c;挂接到一台windows server操作系统的服务器。 EVA存储上有三个硬盘指示灯亮黄灯&#xff0c;此刻存储还能正常使用。管理员在更换硬盘的过程中&#xff0c;又出现一块硬盘对应的指示灯亮黄…

Linux 网络基础

文章目录 1. 计算机网络背景2. 协议2.1 OSI七层模型2.2 为什么要有TCP/IP协议&#xff1f; 3. 协议与操作系统的关系4. 网络传输基本流程4.1 局域网通信原理4.2 局域网通信流程4.3 跨网络通信流程 5. Socket编程预备知识5.1 端口号5.2 网络字节序5.3 socket编程接口 6. 网络命令…

一站式指导:在Neo4j与PostgreSQL间实现高效数据同步

作者&#xff1a;后端小肥肠 &#x1f347; 我写过的文章中的相关代码放到了gitee&#xff0c;地址&#xff1a;xfc-fdw-cloud: 公共解决方案 &#x1f34a; 有疑问可私信或评论区联系我。 &#x1f951; 创作不易未经允许严禁转载。 姊妹篇&#xff1a; 数据同步的艺术&#…

AI一键生成原创圣诞印花图案

一、引言 随着科技的飞速发展&#xff0c;AI 已经深入到我们生活和工作的各个角落&#xff0c;为创意设计领域带来了前所未有的变革。在圣诞即将来临之际&#xff0c;想要设计独特的圣诞印花图案却又担心缺乏灵感或专业技能&#xff1f;别担心&#xff0c;千鹿 AI 为我们提供了…

视频 的 音频通道提取 以及 视频转URL 的在线工具!

视频 的 音频通道提取 以及 视频转URL 的在线工具&#xff01; 工具地址: https://www.lingyuzhao.top/toolsPage/VideoTo.html 它提供了便捷的方法来处理视频文件&#xff0c;具体来说是帮助用户从视频中提取音频轨道&#xff0c;并将视频转换为可以通过网络访问的URL链接。无…

图片的懒加载

目录 懒加载的来源 事件监听 IntersectionObserver 懒加载的来源 图片的来加载其实就是延迟加载&#xff0c;我们知道浏览器的可视范围是有限的&#xff0c;现在网页的内容越来越丰富&#xff0c;一般网页的内容都是需要滚动才能完成浏览 如果网页有很多图片&#xff0c;然…