当前位置: 首页 > news >正文

Leetcode刷题4--- 寻找两个正序数组的中位数 Python

目录

  • 题目及分析
  • 方法一:直接合并后排序
  • 方法二:二分查找法

题目及分析

(力扣序号4:[寻找两个正序数组的中位数](https://leetcode.cn/problems/median-of-two-sorted-arrays/description/)
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数

示例 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 == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

方法一:直接合并后排序

思路分析:

  1. 将两个数组合并成一个数组。
  2. 对合并后的数组进行排序。
  3. 找到排序后数组的中位数。
    a. 如果合并后的数组长度是奇数,中位数就是数组中间那个元素。
    b. 如果合并后的数组长度是偶数,中位数就是数组中间两个元素的平均值。
def findMedianSortedArrays(nums1, nums2):# 合并两个数组merged_array = nums1 + nums2# 对合并后的数组进行排序merged_array.sort()# 获取合并后的数组长度length = len(merged_array)# 判断长度的奇偶性,并返回中位数if length % 2 == 1:return merged_array[length // 2]else:return (merged_array[length // 2 - 1] + merged_array[length // 2]) / 2.0

方法二:二分查找法

思路分析:

  1. 使用二分查找法,在较短的数组上进行二分查找。
  2. 设定两个数组的分割线,使得分割线左边的元素总数等于分割线右边的元素总数。
  3. 比较分割线左边和右边的元素,调整分割线位置,直到找到合适的分割线。
  4. 计算并返回中位数。
def findMedianSortedArrays(nums1, nums2):# 保证nums1是较短的数组if len(nums1) > len(nums2):nums1, nums2 = nums2, nums1m, n = len(nums1), len(nums2)imin, imax, half_len = 0, m, (m + n + 1) // 2while imin <= imax:i = (imin + imax) // 2j = half_len - iif i < m and nums2[j-1] > nums1[i]:imin = i + 1elif i > 0 and nums1[i-1] > nums2[j]:imax = 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:return max_of_leftif 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.0

相关文章:

Leetcode刷题4--- 寻找两个正序数组的中位数 Python

目录 题目及分析方法一&#xff1a;直接合并后排序方法二&#xff1a;二分查找法 题目及分析 &#xff08;力扣序号4&#xff1a;[寻找两个正序数组的中位数](https://leetcode.cn/problems/median-of-two-sorted-arrays/description/&#xff09; 给定两个大小分别为 m 和 n …...

springBoot(若依)集成camunda

1、下图为项目结构 2、最外层 pom引入依赖 <properties><!--camunda 标明版本&#xff0c;注意要个自己的Spring 版本匹配&#xff0c;匹配关系自行查询官网--><camunda.version>7.18.0</camunda.version> </properties> 3、common模块引入依赖 …...

【微信小程序知识点】自定义构建npm

在实际开发中&#xff0c;随着项目的功能越来越多&#xff0c;项目越来越复杂&#xff0c;文件目录也变得很繁琐&#xff0c;为了方便进行项目的开发&#xff0c;开发人员通常会对目录结构进行优化调整&#xff0c;例如&#xff1a;将小程序源码放到miniprogram目录下。 &…...

JCR一区 | Matlab实现GAF-PCNN-MATT、GASF-CNN、GADF-CNN的多特征输入数据分类预测/故障诊断

JJCR一区 | Matlab实现GAF-PCNN-MATT、GASF-CNN、GADF-CNN的多特征输入数据分类预测/故障诊断 目录 JJCR一区 | Matlab实现GAF-PCNN-MATT、GASF-CNN、GADF-CNN的多特征输入数据分类预测/故障诊断分类效果格拉姆矩阵图GAF-PCNN-MATTGASF-CNNGADF-CNN 基本介绍程序设计参考资料 分…...

新手教学系列——高效管理MongoDB数据:批量插入与更新的实战技巧

前言 在日常开发中,MongoDB作为一种灵活高效的NoSQL数据库,深受开发者喜爱。然而,如何高效地进行数据的批量插入和更新,却常常让人头疼。今天,我们将一起探讨如何使用MongoDB的bulk_write方法,简化我们的数据管理流程,让代码更加简洁高效。 常规做法:find、insertone…...

C# Winform 自定义事件实战

在C#的WinForms中&#xff0c;自定义事件是一种强大的工具&#xff0c;它允许你创建自己的事件&#xff0c;从而在特定条件下通知订阅者。自定义事件通常用于封装业务逻辑&#xff0c;使代码更加模块化和易于维护。下面我将通过一个实战例子来展示如何在WinForms中创建和使用自…...

Python通过继承实现多线程

本套课在线学习视频&#xff08;网盘地址&#xff0c;保存到网盘即可免费观看&#xff09;&#xff1a; ​​https://pan.quark.cn/s/677661ea63b3​​ 本节将介绍如何利用Python中的thread模块和threading模块实现多线程&#xff0c;并通过继承threading.Thread类并重写run方…...

记一次项目经历

一、项目需求 1、设备四个工位&#xff0c;每个工位需要测试产品的电参数&#xff1b; 2、每个另外加四个位置温度&#xff1b; 3、显示4个通道电流曲线&#xff0c;16个通道温度曲线&#xff1b; 4、可切换工艺参数&#xff1b; 5、常规判定&#xff0c;测试数据保存到表格内&…...

Elasticsearch 8 支持别名查询

在 Elasticsearch 8 中&#xff0c;使用 Java 高级 REST 客户端进行别名管理的过程与之前的版本类似&#xff0c;但有一些API细节上的变化。以下是如何使用 Java 和 Elasticsearch 8 进行别名操作的例子&#xff1a; 引入依赖 确保你的项目中包含了 Elasticsearch 的高级 RES…...

【Spring Cloud】 使用Eureka实现服务注册与服务发现

文章目录 &#x1f343;前言&#x1f38d;解决方案&#x1f6a9;关于注册中⼼&#x1f6a9;CAP理论&#x1f6a9;常见的注册中心 &#x1f384;Eureka&#x1f6a9;搭建 Eureka Server&#x1f388;创建Eureka-server ⼦模块&#x1f388;引入依赖&#x1f388;项目构建插件&am…...

JDK安装详细教程(以JDK17为例)

一、JDK的下载 1. 前往oracle官网下载JDK Java Archive Downloads - Java SE 17 在这里选择对应的JDK版本&#xff0c;我这里就直接选择JDK17的版本了。 然后下载对应的软件包&#xff0c;我这里采用的是Windows的安装程序。 点击上述圈起来的链接即可下载安装包&#xff0c;…...

安装nodejs | npm报错

nodejs安装步骤: 官网&#xff1a;https://nodejs.org/en/ 在官网下载nodejs: 双击下载下来的msi安装包&#xff0c;一直点next&#xff0c;我选的安装目录是默认的: 测试是否安装成功&#xff1a; 输入cmd打开命令提示符&#xff0c;输入node -v可以看到版本&#xff0c;说…...

聊点基础---Java和.NET开发技术异同全方位分析

1. C#语言基础 1.1 C#语法概览 欢迎来到C#的世界&#xff01;对于刚从Java转过来的开发者来说&#xff0c;你会发现C#和Java有很多相似之处&#xff0c;但C#也有其独特的魅力和强大之处。让我们一起来探索C#的基本语法&#xff0c;并比较一下与Java的异同。 程序结构 C#程序…...

【C++】C++中SDKDDKVer.h和WinSDKVer.h函数库详解

目录 一.SDKDDKVer.h介绍 二.WinSDKVer.h介绍 三.WinSDKVer.h 和 SDKDDKVer.h 的区别 一.SDKDDKVer.h介绍 SDKDDKVer.h 是一个在 Windows 软件开发中常见的头文件&#xff0c;它用于定义软件开发工具包&#xff08;SDK&#xff09;和驱动开发工具包&#xff08;DDK&…...

uni-app 蓝牙传输

https://www.cnblogs.com/ckfuture/p/16450418.html https://www.cnblogs.com/yangxiaobai123/p/16021058.html 字符串转base64&#xff1a;https://www.cnblogs.com/sunny3158/p/17312158.html 将 ArrayBuffer 对象转成 Base64 字符串&#xff1a;基础 - uni.arrayBufferT…...

MBR10200CT-ASEMI智能AI应用MBR10200CT

编辑&#xff1a;ll MBR10200CT-ASEMI智能AI应用MBR10200CT 型号&#xff1a;MBR10200CT 品牌&#xff1a;ASEMI 封装&#xff1a;TO-220 批号&#xff1a;最新 恢复时间&#xff1a;35ns 最大平均正向电流&#xff08;IF&#xff09;&#xff1a;10A 最大循环峰值反向…...

力扣 爬楼梯

动态规划算法基础篇。 class Solution {public int climbStairs(int n) {int[] f new int[n 1];f[0] 1;f[1] 1;//当爬到n阶楼梯时&#xff0c;可知是由n-1阶或n-2阶楼梯而来for(int i 2; i < n; i) {f[i] f[i - 1] f[i - 2];//后面的每一阶种数由前两个状态得到}ret…...

java设计模式之:策略模式+工厂模式整合案例实战(一)

本文介绍项目中常用的策略模式工厂模式的案例&#xff0c;该案例是针对策略类比较少的情况&#xff1b;下一篇会讲解策略类比较多的案例&#xff0c;下面直接开始&#xff1a; 案例1&#xff1a;项目中对系统中的客户和销售进行事件通知(短信、邮件、钉钉) 首先要有通知的策略…...

国内Ubuntu安装 stable-diffusion教程,换成国内镜像

安装依赖&#xff1a; 首先更新系统并安装Python 3.10和pip&#xff1a; sudo apt update sudo apt install python3.10 python3-pip 设置Python虚拟环境&#xff08;可选&#xff09;&#xff1a; 安装Python虚拟环境管理工具&#xff0c;并创建激活虚拟环境&#xff1a; su…...

JAVA final详细介绍

一、介绍 final 中文意思: 最后的,最终的. final 可以修饰类、属性、方法和局部变量, 在某些情况下,程序员可能有以下需求&#xff0c;就会使用到final&#xff1a; 1&#xff09;当不希望类被继承时,可以用final修饰。 //如果我们要求A类不能被其他类继承 //可以使用fin…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...

深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向

在人工智能技术呈指数级发展的当下&#xff0c;大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性&#xff0c;吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型&#xff0c;成为释放其巨大潜力的关键所在&…...