leetcode-4. 寻找两个正序数组的中位数

题目描述

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

算法的时间复杂度应该为 O(log (m+n)) 。

示例 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

思路

二分查找,参考官方题解

class Solution(object):"""- 主要思路:要找到第 k (k>1) 小的元素,那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较- 这里的 "/" 表示整除- nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个- nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个- 取 pivot = min(pivot1, pivot2),两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个- 这样 pivot 本身最大也只能是第 k-1 小的元素- 如果 pivot = pivot1,那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除",剩下的作为新的 nums1 数组- 如果 pivot = pivot2,那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除",剩下的作为新的 nums2 数组- 由于我们 "删除" 了一些元素(这些元素都比第 k 小的元素要小),因此需要修改 k 的值,减去删除的数的个数"""def get_mid(self, k, nums1, nums2):index1,index2 = 0, 0while True:if index1 == len(nums1):return nums2[index2+k-1]if index2 == len(nums2):return nums1[index1+k-1]if k==1:return min(nums1[index1],nums2[index2])newindex1 = min(index1+k//2-1, len(nums1)-1)newindex2 = min(index2+k//2-1, len(nums2)-1)if nums1[newindex1]<=nums2[newindex2]:k -= newindex1-index1+1index1 = newindex1+1else:k-= newindex2-index2+1index2 = newindex2+1def findMedianSortedArrays(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: float"""total = len(nums1)+ len(nums2)if total % 2 == 1:return self.get_mid(total//2+1, nums1, nums2)else:return (self.get_mid(total//2, nums1, nums2) + self.get_mid(total//2+1, nums1, nums2)) / 2.0if __name__ == '__main__':s = Solution()nums1 = [1,2,3,4,5]nums2 = [6,7,8,9,10,11,12,13,14,15,16,17]print(s.findMedianSortedArrays(nums1, nums2))

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

婚礼弹幕上墙阳光正好,爱意正浓,打造一场出圈的唯美婚礼!

原文地址 婚礼现场的弹幕功能可以给整个场景增添温暖和喜庆的氛围。通过手机发送祝福&#xff0c;让亲友可以即时将祝福传达给新人&#xff0c;同时这些祝福以弹幕的形式在大屏幕上滚动展示&#xff0c;增加了现场互动的乐趣。墙上新闻搭配的功能则更加抢眼&#xff0c;不仅可…

基于代理的分布式身份管理方案

目的是使用分布式的联合计算分发去替换掉区块链中原有的类第三方可信中心的证书机制&#xff0c;更加去中心化。 GS-TBK Group Signatures with Time-bound Keys. CS-TBK 算法 Complete subtree With Time-bound Keys&#xff0c;该算法是用来辅助检测用户的签名是否有效&…

LabVIEW提高开发效率技巧----使用快捷键

在LabVIEW的开发过程中&#xff0c;熟练掌握和运用快捷键可以极大地提升工作效率&#xff0c;减少重复性操作所花费的时间。快捷键不仅可以加快编程速度&#xff0c;还能让开发者更加专注于逻辑实现和功能设计。细问问将详细介绍LabVIEW中的常用快捷键&#xff0c;特别是强大的…

【变化检测】基于HANet建筑物(LEVIR-CD)变化检测实战及ONNX推理

主要内容如下&#xff1a; 1、LEVIR-CD数据集介绍及下载 2、运行环境安装 3、HANet模型训练与预测 4、Onnx运行及可视化 运行环境&#xff1a;Python3.8&#xff0c;torch1.12.0cu113&#xff0c;onnxruntime1.19.2【这里装CPU版&#xff0c;GPU版低于1.19.2算子报错】 likyo…

一招解决微软copilot提示:该服务在您所在的地区不可用

随着windows 11的推出很多网友都开始注意到了微软copilot AI助手。科技快速发展当前AI已经是一个家喻户晓的名词了, 尤其是一些之前体验过ai强大功能的用户&#xff0c;对AI更加是爱不释手。虽然win 11 版本已经将copilot集成到系统当中&#xff0c;然后不少网友在想要体验时却…

kali里面搭建docker容器

注意事项&#xff1a;kali版本&#xff0c;镜像源 &#xff08;1&#xff09;权限为管理员&#xff1a; sudo su (2) 更新软件包列表并升级已安装的软件包 apt-get update apt-get upgrade 出错了&#xff0c;应该是更新源出问题了。 &#xff08;3&#xff09;更换镜像源&am…

stm32开发之串口空闲中断和环形数组的最简单的组合使用

前言 本次使用的是lwrb开源的源码&#xff1b;测试环境使用的是stm32f407zgt6这里不介绍lwrb的内容&#xff0c;如有需要请自行去查阅.这里会使用到rt_container_of的宏定义(相关介绍请参考rt_thread或linux源码相关的宏定义,其表达的内容是一致的)这里使用的是threadx做为os本…

Java调用数据库 笔记05

一. 数据库&#xff08;通过各种驱动来实现调用&#xff09;&#xff1a; &#xff08;应用程序通过接口控制的各种数据库驱动来调用数据库-->jdbc方法&#xff09; 1.创建Java的普通class类 2.加载驱动 Class.forName("com.mysql.jdbc.Driver"); 3.驱动管理类…

TCP并发服务器的实现

一请求一线程 问题 当客户端数量较多时&#xff0c;使用单独线程为每个客户端处理请求可能导致系统资源的消耗过大和性能瓶颈。 资源消耗&#xff1a; 线程创建和管理开销&#xff1a;每个线程都有其创建和销毁的开销&#xff0c;特别是在高并发环境中&#xff0c;这种开销…

开源 AI 智能名片链动 2+1 模式 O2O 商城小程序在社群活动中的应用与时机选择

摘要&#xff1a;本文探讨了开源 AI 智能名片链动 21 模式 O2O 商城小程序在社群经济中的重要性&#xff0c;着重分析了如何借助该小程序适时举办大型活动以维持和引爆社群活跃度。通过对活动时机选择的研究&#xff0c;强调了针对社群用户量身定制活动时机的必要性&#xff0c…

简单了解微服务--黑马(在更)

认识微服务 单体架构 不适合大型复杂项目 微服务架构 将单体结构的各个功能模块拆分为多个独立的项目 拆取的独立项目分别开发&#xff0c;在部署的时候也要分别去编译打包&#xff0c;分别去部署&#xff0c;不同的模块部署在不同的服务器上&#xff0c;对外提供不同的功能…

渗透测试入门学习——php表单form与POST、GET请求练习

最终效果&#xff1a; 必填项为空报错提示&#xff1a; 代码&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>php表单练习</title> </head> <body> <?php//php中的…

UE5学习笔记22-武器瞄准和武器自动开火

0、一些疑问的记录 1.UUserWidget类和AHUD类的区别。两者都是关于界面显示的类。 实践&#xff1a; 想让界面和用户有交互使用UUserWidget&#xff0c;如果不要交互只是显示使用AHUD类&#xff0c;例如使用UUserWidget类制作开始界面&#xff0c;游戏开始&#xff0c;游戏设置&…

计算机人工智能前沿进展-大语言模型方向-2024-09-17

计算机人工智能前沿进展-大语言模型方向-2024-09-17 1. Large Language Models in Biomedical and Health Informatics: A Review with Bibliometric Analysis H Yu, L Fan, L Li, J Zhou, Z Ma, L Xian, W Hua, S He… - Journal of Healthcare …, 2024 生物医学和健康信息…

部分动态铜皮的孤岛无法删除。报错

(SPMHCI-1): Cannot break shape into fragments. 网上寻找了很多答案&#xff0c;都不太理想&#xff0c;不是我想要的方法。 终于功夫不负有心人&#xff0c;在Cadence官方论坛找到了蛛丝马迹。 Breaking Static shape into fragments - PCB Design - PCB Design & IC …

深入解析Transformer原理

在自然语言处理&#xff08;NLP&#xff09;领域&#xff0c;Transformer架构的出现无疑是一个里程碑式的进展。从Google的BERT到OpenAI的GPT系列&#xff0c;Transformer已经成为许多前沿AI模型的核心。今天&#xff0c;我们就来深入探讨Transformer的原理&#xff0c;帮助你更…

优惠充值话费api对接如何选择对接平台?

优惠充值话费接口通常由电信运营商、第三方支付平台或专业的充值服务提供商提供。这些平台通过API接口允许开发者将话费充值功能集成到应用程序或网站中。 选择哪个平台比较好&#xff0c;取决于以下几个因素&#xff1a; 覆盖范围&#xff1a;选择能够覆盖你需要服务的地区和…

深度学习-生成式检索-论文速读-2024-09-14

深度学习-生成式检索-论文速读-2024-09-14 前言: 生成式检索&#xff08;Generative Retrieval&#xff0c; GR&#xff09;是一种结合了生成模型和检索系统的人工智能技术方法。这种方法在处理信息检索任务时&#xff0c;不仅依赖于已有数据的检索&#xff0c;还能生成新的、…

c++基类和派生类对象的赋值转换——赋值兼容规则

1.引出 如下场景&#xff1a; 由于b是double类型&#xff0c;所以赋值给int类型的引用前&#xff0c;要先进行隐式类型转换&#xff0c;这中间会生成临时对象&#xff0c;类是对象具有常性&#xff0c;所以int&之前应该加上const。 但是下面的场景&#xff1a; 没有出现报…

Python3网络爬虫开发实战(16)分布式爬虫(第一版)

文章目录 一、分布式爬虫原理1.1 分布式爬虫架构1.2 维护爬取队列1.3 怎样来去重1.4 防止中断1.5 架构实现 二、Scrapy-Redis 源码解析2.1 获取源码2.2 爬取队列2.3 去重过滤2.4 调度器 三、Scrapy 分布式实现3.1 准备工作3.2 搭建 Redis 服务器3.3 部署代理池和 Cookies 池3.4…