LeetCode 力扣: 寻找两个正序数组的中位数 (Javascript)
LeetCode力扣双指针题目
主要提供了力扣热题第四题,使用js,复杂度O(log(m+n)),寻找两个正序数组的中位数。
题目解析
题目要求在两个已排序数组 nums1 和 nums2 中找到它们的中位数。为了满足时间复杂度要求 O(log (m+n)),可以采用双指针的方法合并这两个数组,然后计算中位数。
思路
首先,代码检查 nums1 和 nums2 的长度,确保 nums1 总是较短的数组。如果 nums1 的长度大于 nums2,则通过递归调用 findMedianSortedArrays 函数,将它们的顺序反转,以确保 nums1 始终是较短的数组。
获取 nums1 和 nums2 的长度,分别赋值给 x 和 y。
初始化两个指针 low 和 high,它们将用于执行二分查找。low 初始为0,high 初始为 x,即 nums1 的长度。
进入一个循环,循环条件是 low 小于等于 high。
在每次循环迭代中,计算 partitionX 和 partitionY,这两个值将用于将数组分成左右两部分。partitionX 表示将 nums1 分成左右两部分的分界点,而 partitionY 表示将 nums2 分成左右两部分的分界点。这些分界点是通过位运算和数组长度计算得出的。
根据分界点,获取左右两部分的最大值和最小值。maxX 和 minX 表示 nums1 中左右两部分的最大值和最小值,而 maxY 和 minY 表示 nums2 中左右两部分的最大值和最小值。
接着,代码检查最大值和最小值是否满足中位数的条件,即 maxX <= minY 和 maxY <= minX。如果满足这些条件,说明找到了中位数的位置。
如果总元素个数是偶数((x + y) % 2 === 0),则中位数是左右两部分的最大值和最小值的平均数;如果总元素个数是奇数,中位数是最大值中的较大值。
如果没有找到中位数的位置,根据情况更新 low 或 high,以继续二分查找。
最终,如果循环结束后仍然没有找到中位数的位置,代码会抛出一个错误,表示输入的数组不是有序的。
代码
function findMedianSortedArrays(nums1, nums2) {if (nums1.length > nums2.length) {return findMedianSortedArrays(nums2, nums1);}const x = nums1.length;const y = nums2.length;let low = 0;let high = x;while (low <= high) {const partitionX = (low + high) >> 1;const partitionY = ((x + y + 1) >> 1) - partitionX;const maxX = (partitionX === 0) ? Number.NEGATIVE_INFINITY : nums1[partitionX - 1];const maxY = (partitionY === 0) ? Number.NEGATIVE_INFINITY : nums2[partitionY - 1];const minX = (partitionX === x) ? Number.POSITIVE_INFINITY : nums1[partitionX];const minY = (partitionY === y) ? Number.POSITIVE_INFINITY : nums2[partitionY];if (maxX <= minY && maxY <= minX) {if ((x + y) % 2 === 0) {return (Math.max(maxX, maxY) + Math.min(minX, minY)) / 2;} else {return Math.max(maxX, maxY);}} else if (maxX > minY) {high = partitionX - 1;} else {low = partitionX + 1;}}throw new Error("Input arrays are not sorted.");
}
代码解析
((x + y + 1) >> 1) - partitionX这段代码是什么意思
((x + y + 1) >> 1) - partitionX 这段代码用于计算 partitionY,即将第二个数组 nums2 分成左右两部分的分界点。让我解释一下这个表达式的含义:
x是第一个数组nums1的长度。y是第二个数组nums2的长度。partitionX是将第一个数组nums1分成左右两部分的分界点。
现在来逐步解释这个表达式:
-
x + y + 1:首先,将两个数组的长度相加,并加1。这是因为在计算中位数时,需要考虑总的元素个数是否为奇数还是偶数。 -
>> 1:然后,对上述结果进行右移一位,相当于除以2。这是因为中位数是将数组分成两部分,左半部分和右半部分,因此需要将总长度分为两半。 -
- partitionX:最后,从上述结果中减去partitionX。partitionX表示将第一个数组nums1分成左右两部分的分界点。减去partitionX的目的是确定第二个数组nums2分成左右两部分的分界点partitionY。
这个表达式的目的是计算如何将两个数组分成左右两部分,以满足中位数的条件。它考虑了两个数组的长度,以确保正确计算中位数的位置。在这种二分查找算法中,partitionX 和 partitionY 的计算是关键,因为它们指导着如何在两个数组中查找中位数的位置。
if (maxX <= minY && maxY <= minX) {这段代码是什么意思
maxX表示第一个数组nums1中分界点partitionX左侧部分的最大值,或者在partitionX为0时为负无穷大。minY表示第二个数组nums2中分界点partitionY右侧部分的最小值,或者在partitionY为y时为正无穷大。maxY表示第二个数组nums2中分界点partitionY左侧部分的最大值,或者在partitionY为0时为负无穷大。minX表示第一个数组nums1中分界点partitionX右侧部分的最小值,或者在partitionX为x时为正无穷大。
这个条件 maxX <= minY && maxY <= minX 检查以下情况是否成立:
-
maxX小于等于minY:即第一个数组左侧部分的最大值小于等于第二个数组右侧部分的最小值。 -
maxY小于等于minX:即第二个数组左侧部分的最大值小于等于第一个数组右侧部分的最小值。
如果这两个条件都成立,意味着已找到中位数的位置,因为左侧部分的元素都小于或等于右侧部分的元素。这是中位数的定义。
在满足这些条件的情况下,根据总元素个数是奇数还是偶数,代码返回相应的中位数值。如果总元素个数是偶数,中位数是左右两部分的最大值和最小值的平均数;如果总元素个数是奇数,中位数是最大值中的较大值。
这个条件判断是整个算法中的核心,用于确定中位数的位置。如果条件不成立,代码将根据情况更新 low 或 high,以继续二分查找,直到找到中位数的位置
总结
希望本文会对你有所帮助,如果有任何疑问可以留言与我沟通。
相关文章:
LeetCode 力扣: 寻找两个正序数组的中位数 (Javascript)
LeetCode力扣双指针题目 主要提供了力扣热题第四题,使用js,复杂度O(log(mn)),寻找两个正序数组的中位数。 题目解析 题目要求在两个已排序数组 nums1 和 nums2 中找到它们的中位数。为了满足时间复杂度要求 O(log (mn)),可以采…...
第 4 部分 — 增强法学硕士的安全性:对越狱的严格数学检验
一、说明 越狱大型语言模型 (LLM)(例如 GPT-4)的概念代表了人工智能领域的一项艰巨挑战。这一过程需要对这些先进模型进行战略操纵,以超越其预先定义的道德准则或运营边界。在这篇博客中,我的目的是剖析数学的复杂性,并…...
Next.js 中的中间件
Next.js 中的中间件 Next.js 中的中间件是一个功能强大的工具,允许开发人员拦截、修改和控制应用程序中的请求和响应流。无论我们是构建服务器渲染的网站还是成熟的 Web 应用程序,了解如何有效使用中间件都可以显着增强项目进出的数据流。本文将从基础知…...
一、C#笔记
1.注释 /*多行注释*/class HelloWorld{ void Hello(){Console.WriteLine("Hello!");//单行注释}} 2.理解语句 2.1方法、语法、语义 2.2使用标识符 标识符语法规则: 只能使用字母(大写和小写)、数字和下划…...
井盖发生位移怎么办?智能井盖传感器效果
井盖位移是一种严重的安全隐患,因为它可能导致道路受阻并干扰正常的交通,还可能对行人和车辆的安全造成威胁。为了有效应对这一问题,智能井盖传感器的应用提供了一种解决方案。智能井盖传感器可以实时监测井盖的位移情况,并在发现…...
go-zero 开发之安装 goctl 及 go-zero 开发依赖
安装 goctl go 版本在 1.16 及以后执行: GO111MODULEon&&go install github.com/zeromicro/go-zero/tools/goctllatestgo 版本在 1.16 之前执行: GO111MODULEon&&go get -u github.com/zeromicro/go-zero/tools/goctllatest验证是否安…...
win11 CUDA(12.3) + cuDNN(12.x) 卸载
win11 CUDA(12.3) cuDNN(12.x)卸载 信息介绍卸载 信息介绍 本文是对应 win11RTX4070Ti 安装 CUDA cuDNN(图文教程) 的卸载 卸载 控制面板 --> 程序 --> 卸载程序 卸载掉图中红框内的,…...
037.Python面向对象_关于抽象类和抽象方法
我 的 个 人 主 页:👉👉 失心疯的个人主页 👈👈 入 门 教 程 推 荐 :👉👉 Python零基础入门教程合集 👈👈 虚 拟 环 境 搭 建 :👉&…...
华为OD机试真题-5G网络建设-2023年OD统一考试(C卷)
题目描述: 现需要在某城市进行5G网络建设,已经选取N个地点设置5G基站,编号固定为1到N,接下来需要各个基站之间使用光纤进行连接以确保基站能互联互通,不同基站之间架设光纤的成本各不相同,且有些节点之间已经存在光纤相连,请你设计算法,计算出能联通这些基站的最小成本…...
【Spring教程25】Spring框架实战:从零开始学习SpringMVC 之 SpringMVC入门案例总结与SpringMVC工作流程分析
目录 1.入门案例总结2. 入门案例工作流程分析2.1 启动服务器初始化过程2.2 单次请求过程 欢迎大家回到《Java教程之Spring30天快速入门》,本教程所有示例均基于Maven实现,如果您对Maven还很陌生,请移步本人的博文《如何在windows11下安装Mave…...
设计模式再探——装饰模式
目录 一、背景介绍二、思路&方案三、过程1.装饰模式简介2.装饰模式的类图3.装饰模式代码4.装饰模式,职责父类拆分的奥义5.装饰模式,部件抽象类的无中生有 四、总结五、升华 一、背景介绍 最近公司在做架构模型的时候,涉及到装饰模式的研…...
【Python必做100题】之第一题(求两数相加)
思路:键盘输入两个数字,求出两个数的和并打印 代码如下: num1 int(input("请输入一个数字:")) num2 int(input("再输入一个数字:")) #求两数相加 result num1 num2 print(f"两数相加的…...
java面试-Dubbo和zookeeper运行原理
远离八股文,面试大白话,通俗且易懂 看完后试着用自己的话复述出来。有问题请指出,有需要帮助理解的或者遇到的真实面试题不知道怎么总结的也请评论中写出来,大家一起解决。 java面试题汇总-目录-持续更新中 分布式注册中心和服务调…...
Rsync+Sersync
服务器相关参数 源服务器 192.168.17.101 目标服务器(同步到的服务器) 192.168.17.103 ##目标服务器配置 ###1、配置rsync服务 1、安装rsync yum -y install rsync 2、配置rsync vim /etc/rsyncd.conf 配置文件内容 uid root gid root use c…...
Leetcode刷题笔记题解(C++):25. K 个一组翻转链表
思路:利用栈的特性,K个节点压入栈中依次弹出组成新的链表,不够K个节点则保持不变 /*** struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) : val(x), next(nullptr) {}* };*/ #include <stack> class Solution { …...
从线性回归到神经网络
目录 一、线性回归关键思想 1、线性模型 2、基础优化算法 二、线性回归的从零开始实现 1、生成数据集 2、读取数据集 3、初始化模型参数 4、定义模型 5、定义损失函数 6、定义优化算法 7、训练 三、线性回归的简洁实现 1、生成数据集 2、读取数据集 3、定义模型…...
LANDSAT_7/02/T1/RAW的Landsat7_C2_RAW类数据集
Landsat7_C2_RAW是指Landsat 7卫星的数据集,采用的是Collection 2级别的数据处理方法,对应的是Tier 1级别的原始数据(RAW)。该数据集包括了Landsat 7卫星从1999年4月15日开始的所有数据,共涵盖了全球范围内的陆地和海洋…...
绕过360给目标机器添加账户
CS BOF是什么? Beacon 对象文件 (BOF) 是一个已编译的 C 程序,按照约定编写,允许其在 Beacon 进程内执行并使用内部 Beacon API。BOF 是一种通过新的利用后功能快速扩展 Beacon 代理的方法。 BOF 的占地面积较小。它们在 Beacon 进程内部运…...
C/C++ 题目:给定字符串s1和s2,判断s1是否是s2的子序列
判断子序列一个字符串是否是另一个字符串的子序列 解释:字符串的一个子序列是原始字符串删除一些(也可以不删除)字符,不改变剩余字符相对位置形成的新字符串。 如,"ace"是"abcde"的一个子序…...
Nginx的stream配置
一、stream模块概要。 stream模块一般用于tcp/UDP数据流的代理和负载均衡,可以通过stream模块代理转发TCP消息。 ngx_stream_core_module模块由1.9.0版提供。 默认情况下,没有构建此模块。 -必须使用-with stream配置参数启用。 也就是说,必…...
OpenClaw自动化周报:Qwen3.5-9B解读工作截图生成总结
OpenClaw自动化周报:Qwen3.5-9B解读工作截图生成总结 1. 为什么需要自动化周报 每周五下午,我都会陷入一种"周报焦虑"——电脑桌面上堆满了会议截图、临时记录的txt文件、微信里的零散对话。手动整理这些碎片信息需要3-4个小时,常…...
【FMCW雷达】频率调制连续波FMCW雷达系统(从波形生成到利用小胞平均常误报率CA-CFAR进行目标检测)【含Matlab源码 15242期】含报告
💥💥💥💥💥💥💥💥💞💞💞💞💞💞💞💞💞Matlab武动乾坤博客之家💞…...
告别命令行:5分钟掌握ffmpegGUI视频处理新方式
告别命令行:5分钟掌握ffmpegGUI视频处理新方式 【免费下载链接】ffmpegGUI ffmpeg GUI 项目地址: https://gitcode.com/gh_mirrors/ff/ffmpegGUI ffmpegGUI是一款创新的跨平台视频处理工具,它将强大的FFmpeg命令行功能转化为直观的图形界面操作&a…...
爬虫自动化(DrissionPage)
目录 ?一.介绍: 下载DrissionPage,还是我们熟悉的pip: 环境准备: ?二.基本代码: 它对于的导包和类使用: 窗口的设置: 和获取的页面的滑动: 3.进一步认识DrissionPage: 浏览器可以多开…...
HunyuanVideo-Foley快速入门:VSCode远程开发与模型调试指南
HunyuanVideo-Foley快速入门:VSCode远程开发与模型调试指南 1. 前言:为什么选择VSCode远程开发? 如果你正在使用HunyuanVideo-Foley这类音效生成模型,可能会遇到这样的困扰:本地机器性能不足,而云服务器虽…...
基于S7-300与组态王的智能药片装瓶机控制系统优化设计
1. 智能药片装瓶机控制系统的核心价值 在制药生产线上,药片装瓶环节看似简单却暗藏玄机。传统的人工装瓶方式不仅效率低下,还容易出现计数错误、交叉污染等问题。我曾在某药企亲眼见过工人因疲劳导致装瓶数量出错,最终整批药品不得不报废的案…...
别再死记硬背了!用C++/Java手把手实现线索二叉树(附完整代码与避坑指南)
从零实现线索二叉树:C/Java双语言实战与陷阱全解析 第一次在面试白板上遇到线索二叉树的实现题时,我的手心全是汗。教科书上的递归图示看起来清晰,但真正要写出无bug的线索化代码时,那些ltag和rtag就像捉迷藏的孩子,总…...
前端 HTML 转 PDF
spdf 两个库转换成 PDF 文件并下载到本地。 简单说:它能让用户 “一键下载” 网页上的某个区域为 PDF(比如报表、数据统计页、合同预览页等),还预留了 “水印功能” 的注释代码(可按需启用)。 核心依赖说…...
开源!手搓ESP-VoCat 喵伴桌面AI助手,帮你养萌宠 OpenClaw龙虾,内置豆包,会听、会动、会陪伴
模组选型:ttps://item.taobao.com/item.htm?ftt&id1033585120956&spma21dvs.23580594.0.0.4fee2c1bAqCiqc&skuId6211360130611 ESP-VoCat 喵伴是乐鑫携手火山引擎扣子大模型团队打造的智能 AI 开发套件,适用于玩具、智能音箱、智…...
便利店老板的备货神器——基于粒子群优化支持向量机的单日关东煮销量预测
基于粒子群优化支持向量机(PSO-SVM)的时间序列预测 PSO-SVM时间序列 matlab代码暂无Matlab版本要求 -- 推荐 2018B 版本及以上 采用 Libsvm 工具箱(无需安装,可直接运行),仅支持 Windows 64位系统昨天便利店刚进了一箱新口味的魔芋…...
