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

力扣经典二分题：4. 寻找两个正序数组的中位数

news 来源：原创 2025/5/9 7:46:53

题目链接：4. 寻找两个正序数组的中位数 - 力扣（LeetCode）

一、题目分析

这道题目是让我们在两个正序的数组中寻找中位数
已知两个数组的大小分别是：int m = nums1.size(),n = nums2.size();
中位数性质1：中位数左侧元素 ≤ 中位数且中位数右侧元素 ≥ 中位数（以升序来看）
中位数性质2：对于一个长度为 N 的数组，中位数将数组一分为二，使得左侧与右侧得元素长度差 ≤ 1
当 m + n 为奇数时，我们需要找到合并后数组中第 k + 1 小的元素，其中 k = (m + n) / 2。
当 m + n 为偶数时，我们需要找到合并后数组中第 k 和第 k + 1 小的元素，然后计算它们的平均值，其中 k = (m + n) / 2 - 1（注意这里 k 是基于 0 的索引，所以实际要找的元素位置是 k 和 k + 1）。

二、算法原理讲解

解法一：暴力排序

通过合并排序的原理，通过中位数的性质，可快速得到中位数的下标，较为简单

时间复杂度为O(M+N)，空间复杂度为O(M+N)

解法二：双指针

时间复杂度为O(M+N)，空间复杂度为O(1)

解法三：暴力枚举

解法四：二分优化

三、编写代码

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size(), n = nums2.size();if(m > n) swap(nums1,nums2); // 保证nums1始终是较短数组int k = (m + n + 1) / 2; // 应划分给小数组的个数// 枚举 i [0,m]for(int i = 0;i <= m;i++){int&& j = k - i;// 分割线周围的四个值int a = i == m ? INT_MAX :nums1[i];int b = i == 0 ? INT_MIN :nums1[i-1];cout << i << ' ' << j << endl;int c = j == n ? INT_MAX :nums2[j];int d = j == 0 ? INT_MIN :nums2[j-1];// 分割线是否合法if(b <= c && d <= a){if((m + n) % 2 == 1) return max(b,d);else return (double)(max(b,d) + min(c,a)) / 2;}}return 1314.521;}
};

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {// 保证nums1始终是较短数组if(nums1.size() > nums2.size()) swap(nums1,nums2);// 应划分给小数组的个数int k = (nums1.size() + nums2.size() + 1) / 2; // 枚举nums1数组中应该划分给小数组的元素个数（二分优化）int left = 0,right = nums1.size();while(left < right){// mid ∈ [0,m]int i = (left + right + 1) / 2; int j = k - i;cout << i << endl;if(nums1[i-1] <= nums2[j]) left = i;else right = i - 1;}// 分割线两边的值int a = left == nums1.size() ? INT_MAX :nums1[left];int b = left == 0 ? INT_MIN :nums1[left-1];int c = (k-left) == nums2.size() ? INT_MAX :nums2[k-left];int d = (k-left) == 0 ? INT_MIN :nums2[k-left-1];// 处理数据+返回if((nums1.size() + nums2.size()) % 2 == 1) return max(b,d);else return (double)(max(b,d) + min(c,a)) / 2;}
};

力扣经典二分题：4. 寻找两个正序数组的中位数

题目链接：4. 寻找两个正序数组的中位数 - 力扣（LeetCode） 一、题目分析这道题目是让我们在两个正序的数组中寻找中位数已知两个数组的大小分别是：int m nums1.size(),n nums2.size();中位数性质1：中位数左侧元素 …...

编程日记 2025/5/9 7:46:53

Java Web开发进阶——Spring Boot与Spring Data JPA

Spring Data JPA 是 Spring 提供的一种面向数据访问的持久化框架，它简化了 JPA 的实现，为开发者提供了一种快速操作数据库的方式。在结合 Spring Boot 使用时，开发者能够快速完成数据库访问层的开发。 1. 介绍Spring Data JPA 1.1 什么是Spr…...

编程日记 2025/5/9 7:41:17

PySpark用sort-merge join解决数据倾斜的完整案例

假设有两个大表 table1 和 table2 ，并通过 sort-merge join 来解决可能的数据倾斜问题。 from pyspark.sql import SparkSession from pyspark.sql.functions import col# 初始化SparkSession spark SparkSession.builder.appName("SortMergeJoinExample&quo…...

编程日记 2025/5/9 7:31:59

【2025 Rust学习 --- 11 实用工具特型01】

清理特型Drop 当一个值的拥有者消失时，Rust 会丢弃（drop）该值。丢弃一个值就必须释放该值拥有的任何其他值、堆存储和系统资源。丢弃可能发生在多种情况下： 当变量超出作用域时；在表达式语句的末尾；当…...

编程日记 2025/5/9 6:35:40

关于Linux PAM模块下的pam_listfile

讲《Linux下禁止root远程登录访问》故事的时候，说好会另开一篇讲讲pam_listfile。我们先看看pam_listfile的man文档怎么介绍的。下面这些就好比人物的简介，甚是恼人；让人看得不明就里，反正“他大舅他二舅都是他舅”。可以直接跳…...

编程日记 2025/5/8 17:25:55

根据中文名称首字母进行分组

很多项目中，需要用到中文名称到首字母进行分组，例如：城市、游戏等等。。。 /*** 将集合数据按照汉字首字母分组排序** param list* return*/public Map<String, Object> screenManufacturer(List<Game> list) {Set<String>…...

编程日记 2025/5/9 7:04:54

springboot 集成 etcd

springboot 集成 etcd 往期内容 ETCD 简介docker部署ETCD 前言好久不见各位小伙伴们，上两期内容中，我们对于分布式kv存储中间件有了简单的认识，完成了docker-compose 部署etcd集群以及可视化工具 etcd Keeper，既然有了认识&a…...

编程日记 2025/5/3 9:07:07

人工智能-数据分析及特征提取思路

1、概况基于学生行为数据预测是否涉黄、涉黑等。 2.数据分析数据分析的意义包括得到数据得直觉、发掘潜在的结构、提取重要的变量、删除异常值、检验潜在的假设和建立初步的模型。 2.1数据质量分析 2.1.1数据值分析查看数据类型： 首先明确各字段的数据类型…...

编程日记 2025/5/9 7:37:08

设计模式行为型状态模式（State Pattern）与常见技术框架应用解析

状态模式（State Pattern）是一种行为型设计模式，它允许对象在内部状态改变时改变其行为，使得对象看起来好像修改了它的类。这种设计模式的核心思想是将对象的状态和行为封装成不同的状态类，通过状态对象的行为改变来避免…...

编程日记 2025/5/9 7:07:55

Android 系统签名 keytool-importkeypair

要在 Android 项目中使用系统签名并将 APK 打包时与项目一起打包，可以按照以下步骤操作： 步骤 1：准备系统签名文件从 Android 系统源码中获取系统签名文件，通常位于 build/target/product/security 目录下，包括 pla…...

编程日记 2025/5/9 7:06:21

ubuntu22.04 gcc,g++从10.5切换到低版本9.5

一、安装gcc-9.5 mkdir gcc cd gcc sudo apt-get download $(apt-cache depends --recurse --no-recommends --no-suggests --no-conflicts --no-breaks --no-replaces --no-enhances --no-pre-depends gcc-9 | grep -v i386 | grep "^\w") sudo dpkg -i *.deb sudo…...

编程日记 2025/5/9 7:41:17

Microsoft 已经弃用了＜experimental/filesystem＞头文件

#define _CRT_SECURE_NO_WARNINGS 1 #define _SILENCE_EXPERIMENTAL_FILESYSTEM_DEPRECATION_WARNING 1 //Microsoft 已经弃用了 <experimental / filesystem> 头文件，并计划在将来移除它。取而代之的是 C17 标准引入的 //<filesystem> 头文件&#xf…...

编程日记 2025/5/9 7:01:46

git 提交命令记录

1.已有本地和远程仓库查看仓库远程地址: git remote -v 大量提交 git add . git commit -m "提交说明" git push 之后输入用户名密码删除文件 git rm 文件名替代git add 后面一样 2.全新提交新建远程仓库 git init touch README.md git add . …...

编程日记 2025/5/9 7:33:19

Unity + Firebase + GoogleSignIn 导入问题

我目前使用 Unity版本：2021.3.33f1 JDK版本为：1.8 Gradle 版本为：6.1.1 Firebase 版本: 9.6.0 Google Sign In 版本为： 1.0.1 问题1 ：手机点击登录报错 apk转化成zip，解压，看到/lib/armeabi-v…...

编程日记 2025/5/9 7:24:34

深度学习的加速器：Horovod，让分布式训练更简单高效！

什么是 Horovod？ Horovod 是 Uber 开发的一个专注于深度学习分布式训练的开源框架，旨在简化和加速多 GPU、多节点环境下的训练过程。它以轻量级、易用、高性能著称，特别适合需要快速部署分布式训练的场景。Horovod 的名字来源于俄罗斯传统舞…...

编程日记 2025/5/9 7:10:39

AI刷题-异或编码、拼凑单词 chi

目录一、异或编码问题描述测试样例解题思路： 问题理解解题思路数据结构选择算法步骤最终代码： 运行结果： 二、拼凑单词 chi 问题描述测试样例解题思路： 问题理解数据结构选择算法步骤最终代码&a…...

编程日记 2025/5/9 7:39:52

xml简介

目录基本语法特点及应用场景一个简单示例 xml（全称eXtensible Markup Language）是一种用于存储和传输数据的标记语言，跨平台并且跨语言，xml内容较多，这篇文章会介绍一些基础的内容。基本语法 xml文档通常以xml声明开…...

编程日记 2025/5/9 2:16:19

MYSQL------MySQL 复制MySQL Cluster 架构

MySQL 复制安装配置主服务器配置首先，在主服务器的配置文件（my.cnf 或 my.ini）中添加以下基本配置： [mysqld] server-id 1 log-bin /var/log/mysql/mysql-bin.logserver-id：为服务器分配唯一的标识&#xff0…...

编程日记 2025/5/8 11:16:37

【人工智能】用Python构建图像分类模型：从TensorFlow到PyTorch的全面指南

随着深度学习在计算机视觉领域的迅猛发展，图像分类作为其核心任务之一，受到了广泛的关注。本文旨在详细介绍如何使用Python构建图像分类模型，从TensorFlow到PyTorch两个主流深度学习框架进行全面对比与实践。文章首先回顾了图像分类的基本概念…...

编程日记 2025/5/5 17:36:07

计算机网络笔记数据链路层 2

1,信道划分： (1)时分复用TDM 将时间等分为“TDM帧”，每个TDM帧内部等分为m个时隙，m个用户对应m个时隙缺点：每个节点只分到了总带宽的1/m,如果有部分的1节点不发出数据，那么就会在这个时间信道被闲置，利用…...

编程日记 2025/5/9 7:18:35

2024年度漏洞态势分析报告，需要访问自取即可!(PDF版本)

2024年度漏洞态势分析报告，需要访问自取即可!(PDF版本),大家有什么好的也可以发一下看看...

编程日记 2025/5/9 5:54:40

Apache Hop从入门到精通第一课揭开Apache Hop神秘面纱

一、Apache Hop是什么？ 1、Apache Hop，简称Hop，全称为Hop Orchestration Platform，即Hop 工作编排平台，是一个数据编排和数据工程平台，旨在促进数据和元数据编排的所有方面。Hop让你专注于你想要解决的问题…...

编程日记 2025/5/9 6:34:14

Unity 人体切片三维可视化，可任意裁切切割。查看不同断层的图像。

Unity 人体切片三维可视化，真彩色，可任意裁切切割。查看不同断层的图像。点击查看效果: 视频效果...

编程日记 2025/5/9 7:34:29

ModuleNotFoundError: No module named ‘podm.metrics‘报错等解决方法

ModuleNotFoundError: No module named podm.metrics’报错等解决方法 podm.metrics 在运行时报错： ModuleNotFoundError: No module named ‘podm.metrics’ 安装了podm后还是报错解决方法： 查看安装位置查看podm的安装位置，并打开到该…...

编程日记 2025/5/9 7:21:36

Java虚拟机运行时数据区域（内存模型）

程序计数器（线程私有内存） What：程序计数器是一块较小的内存空间，可以看作是当前线程所执行的字节码的行号指示器。程序控制流的指示器， 分支，循环，跳转，异常处理，线程…...

编程日记 2025/5/9 2:17:45

trf 4.10安装与使用-生信工具42

01 背景 DNA 中的串联重复（Tandem Repeat）指的是两个或多个相邻且近似的核苷酸模式的拷贝。Tandem Repeats Finder (TRF) 是一个程序，用于定位并显示 DNA 序列中的串联重复。用户只需提交一个以 FASTA 格式编写的序列，无需指定重…...

编程日记 2025/5/9 6:57:19

rom定制系列------小米max3安卓12 miui14批量线刷默认开启usb功能选项插电自启等

小米Max3是小米公司于2018年7月19日发布的机型。此机型后在没有max新型号。采用全金属一体机身设计，配备6.9英寸全面屏.八核处理器骁龙636，后置双摄像头1200万500万像素，前置800万像素.机型代码 ：nitrogen.官方最终版为稳定版12.5…...

编程日记 2025/5/9 6:38:25

PySide6-UI界面设计

导论： PySide6和PyQt都是Python对Qt框架的绑定，允许开发者使用Qt创建平台的GUI应用程序。如果你正在开发商业项目，或者需要使用最新的QT6特性，PySide6是一个更好的选择。如果你更倾向于一个成熟的社区和丰富的资源，Py…...

编程日记 2025/5/8 12:21:06

Java创建线程的方式有哪些？

创建线程的方式 1. 继承 Thread 类在 Java 中，当你启动一个线程时，实际上是调用了 Thread 类的 start() 方法。这个方法会执行以下几个步骤： 线程的状态转变：调用 start() 方法后，线程的状态从 NEW 转变为 RUNNABL…...

编程日记 2025/5/5 9:19:30

Ubuntu | PostgreSQL | 解决 ERROR: `xmllint` is missing on your system.

解决 sudo apt install apt-file sudo apt-file updatesudo apt-file search xmllint sudo apt install libxml2-utils执行 # postgres源码安装包解压文件夹中 make install make install问题 make -C src install make[2]: Entering directory /home/postgres/postgresql-1…...

编程日记 2025/5/5 0:59:23

Jenkins pipeline 发送邮件及包含附件

Jenkins pipeline 发送邮件及包含附件设置邮箱开启SMTP服务此处适用163 邮箱开启POP3/SMTP服务通过短信获取TOKEN （保存TOKEN, 后面Jenkins会用到） Jenkins 邮箱设置安装 Build Timestamp插件设置全局凭证 Dashboard -> Manage Jenkins …...

编程日记 2025/5/8 5:04:15

基于深度学习的视觉检测小项目（十）通过样式表改变界面的外观

一、创建色卡模板文件在PS中打开之前创建的色卡文件，用吸管拾色器吸取各个色卡的色彩值： 并保存为JSON文件，color_card.json，文件保存在项目的/settings目录下： {"colors": {"RED": "#dc1…...

编程日记 2025/5/1 13:37:54

【Java基础】Stream流、文件File相关操作，IO的含义与运用

1. Java 流(Stream)、文件(File)和IO Java.io 包几乎包含了所有操作输入、输出需要的类。所有这些流类代表了输入源和输出目标。Java.io 包中的流支持很多种格式，比如：基本类型、对象、本地化字符集等等。一个流可以理解为一个数据的序列。输入流表…...

编程日记 2025/5/4 3:10:25

Java-日志-Slf4j-Log4j-logback

文章目录 SLF4J基础概念使用输出形式日志绑定桥接旧的框架实战 logback基础概念配置文件 Log4j概述 SLF4J 参考： https://www.cnblogs.com/shenStudy/p/15806951.html https://slf4j.org/ 基础概念是什么？SLF4J（Simple Logging Facade fo…...

编程日记 2025/5/8 13:22:11

探索式测试

探索式测试是一种软件测试风格，它强调独立测试人员的个人自由和职责，为了持续优化其工作的价值，将测试学习、测试设计、测试执行和测试结果分析作为相互支持的活动，在整个项目实现过程中并行地执行。选择合适的探索式测试方法我…...

编程日记 2025/5/8 14:28:20

LeetCode LCP17速算机器人

速算机器人：探索字符指令下的数字变换在编程的奇妙世界里，我们常常会遇到各种有趣的算法问题，这些问题不仅考验我们的逻辑思维，还能让我们感受到编程解决实际问题的魅力。今天，就让我们一同探讨一个关于速算机器人的…...

编程日记 2025/5/5 15:48:05

Taro+Vue实现图片裁剪组件

cropper-image-taro-vue3 组件库介绍 cropper-image-taro-vue3 是一个基于 Vue 3 和 Taro 开发的裁剪工具组件，支持图片裁剪、裁剪框拖动、缩放和输出裁剪后的图片。该组件适用于 Vue 3 和 Taro 环境，可以在网页、小程序等平台中使用。源码 https:…...

编程日记 2025/5/4 3:09:53

ISP各模块功能介绍

--------声明，本文为转载整理------- ISP各个模块功能介绍： 各模块前后效果对比： 黑电平补偿（BLC） 在理想情况下，没有光照射的像素点其响应值应为0。但是，由于杂质、受热等其它原因的影响&…...

编程日记 2025/5/7 9:19:07

SQL-leetcode-584. 寻找用户推荐人

584. 寻找用户推荐人表: Customer -------------------- | Column Name | Type | -------------------- | id | int | | name | varchar | | referee_id | int | -------------------- 在 SQL 中，id 是该表的主键列。该表的每一行表示一个客户的 id、姓名以及推…...

编程日记 2025/5/6 10:30:15

新冠肺炎服务预约微信小程序的设计与实现ssm+论文源码调试讲解

第4章系统设计 4.1 系统设计的原则在系统设计过程中，也需要遵循相应的设计原则，这些设计原则可以帮助设计者在短时间内设计出符合设计规范的设计方案。设计原则主要有可靠性，安全性，可定制化，可扩展性，可…...

编程日记 2025/5/7 7:01:13

多模态人工智能在零售业的未来：通过GPT-4 Vision和MongoDB实现智能产品发现

多模态人工智能在零售业的未来：通过GPT-4 Vision和MongoDB实现智能产品发现引言想象一下，顾客在购物时只需上传一张他们所期望的服装或产品的照片，几分钟内便能收到来自他们最喜欢的商店的个性化推荐。这就是多模态人工智能在零售领域所带…...

编程日记 2025/5/1 5:54:09

3D目标检测数据集——kitti数据集

KITTI官网网址：The KITTI Vision Benchmark Suite 下载数据集：The KITTI Vision Benchmark Suite KITTI数据集论文：CMSY9 github可视化代码：GitHub - kuixu/kitti_object_vis: KITTI Object Visualization (Birdview, Volumetric LiDar point cloud )...

编程日记 2025/5/3 4:26:12

从CentOS到龙蜥：企业级Linux迁移实践记录（系统安装）

引言： 随着CentOS项目宣布停止维护CentOS 8并转向CentOS Stream，许多企业和组织面临着寻找可靠替代方案的挑战。在这个背景下，龙蜥操作系统（OpenAnolis）作为一个稳定、高性能且完全兼容的企业级Linux发行版&#xff0…...

编程日记 2025/4/30 13:50:28

Cocos二维Slider

1、可拖动区域计算根据UI的世界坐标了宽高信息计算出handle的坐标范围 this.posMin new Vec2(this.node.worldPosition.x - this.uiSelf.contentSize.width * 0.5, this.node.worldPosition.y - this.uiSelf.contentSize.height * 0.5); this.posMax new Vec2(this.node.w…...

编程日记 2025/5/6 22:57:42

kubeneters-循序渐进Cilium网络（二）

文章目录概要IP 地址配置接口配置解析结论概要接续前一章节，我们还是以这张图继续深入Cilium网络世界 IP 地址配置通过检查 Kubernetes 集群的当前环境，可以获取实际的 IP 地址和配置信息。这些信息将被补充到之前的网络示意图中，以使…...

编程日记 2025/5/3 1:54:48

【再谈设计模式】模板方法模式 - 算法骨架的构建者

一、引言在软件工程、软件开发过程中，我们经常会遇到一些算法或者业务逻辑具有固定的流程步骤，但其中个别步骤的实现可能会因具体情况而有所不同的情况。模板方法设计模式（Template Method Design Pattern）就为解决这类问题提供了…...

编程日记 2025/5/4 11:54:44

[开源]自动化定位建图系统(视频)

系统状态机： 效果展示： 1、机器人建图定位系统-基础重定位，定位功能演示 2、机器人建图定位系统-增量地图构建，手动回环检测演示 3、… 开源链接： https://gitee.com/li-wenhao-lwh/lifelong-backend Qt人机交互…...

编程日记 2025/5/3 1:54:44

Kali系统(Debian 10.3) 遇到的问题

目录问题一：非问题 kali 基础官网与安装问题二： 问题三： Kali系统 MySQL问题Cant connect to local MySQL server through socket /run/mysqld/mysqld.sock (2) 问题四：重新安装MySQL 也就是MariaDB(MariaDB 含 MySQL相关…...

编程日记 2025/5/7 4:07:09