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

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

题目链接: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. 寻找两个正序数组的中位数

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

解决WordPress出现Fatal error: Uncaught TypeError: ftp_nlist()致命问题

错误背景 WordPress版本&#xff1a;wordpress-6.6.2-zh_CN WooCommerce版本&#xff1a;woocommerce.9.5.1 WordPress在安装了WooCommerce插件后&#xff0c;安装的过程中没有问题&#xff0c;在安装完成后提示&#xff1a; 此站点遇到了致命错误&#xff0c;请查看您站点管理…...

Excel 技巧07 - 如何计算到两个日期之间的工作日数?(★)如何排除节假日计算两个日期之间的工作日数?

本文讲了如何在Excel中计算两个日期之间的工作日数&#xff0c;以及如何排除节假日计算两个日期之间的工作日数。 1&#xff0c;如何计算到两个日期之间的工作日数&#xff1f; 其实就是利用 NETWORKDAYS.INTL 函数 - weekend: 1 - 星期六&#xff0c;星期日 2&#xff0c;如…...

快速实现一个快递物流管理系统:实时更新与状态追踪

物流管理是电商、仓储和配送等行业的重要组成部分。随着电子商务的快速发展&#xff0c;快递物流的高效管理和实时状态更新变得尤为关键。本文将演示如何使用Node.js、Express、MongoDB等技术快速构建一个简单的快递物流管理系统&#xff0c;该系统支持快递订单的实时更新和追踪…...

kvm 解决 安装windows 虚拟机cpu 核数问题

通过lscpu命令查到我本机的cpu信息如下 CPU(s): 12 —— 系统的总逻辑处理单元数量&#xff08;包括所有核心和逻辑处理器&#xff09;。Thread(s) per core: 2 —— 每个物理核心支持 2 个线程&#xff08;表示启用了超线程技术&#xff09;。Core(s) per socket: 6 —— 每个…...

Ansys Fluent Aeroacoustics 应用

探索 Ansys Fluent 在气动声学领域的前沿功能&#xff0c;彻底改变各行各业解决降噪和提高音质的方式。 了解气动声学 气动声学是声学的一个分支&#xff0c;它处理湍流流体运动产生的噪声以及这些声音通过流体介质&#xff08;如空气&#xff09;的传播。这个领域在工程中至…...

119.使用AI Agent解决问题:Jenkins build Pipeline时,提示npm ERR! errno FETCH_ERROR

目录 1.Jenkins Build时的错误 2.百度文心快码AI智能体帮我解决 提问1&#xff1a;jenkins中如何配置npm的源 提问2&#xff1a;jenkins pipeline 类型为pipeline script from SCM时&#xff0c;如何配置npm源 3.最终解决方法-Jenkinsfile的修改 4.感触 1.Jenkins Build时…...

istio-proxy内存指标

在 Istio 环境中&#xff0c;istio-proxy 是 Envoy 的边车代理容器。通过运行命令 curl localhost:15000/memory&#xff0c;或者curl localhost:15000/stats 可以查询 Envoy 的内存统计信息。以下是典型返回结果的结构和意义&#xff1a; 返回结果单位是bytes&#xff0c;需/…...

List详解 - 双向链表的操作

在C中&#xff0c;std::list是标准模板库&#xff08;STL&#xff09;中的一个容器&#xff0c;它实现了双向链表的数据结构。与数组或向量&#xff08;std::vector&#xff09;不同&#xff0c;std::list允许在常数时间内进行插入和删除操作&#xff0c;尤其是在链表的任意位置…...

多目标优化算法之一:基于分解的方法

在多目标优化算法中,“基于分解的方法”通常指的是将多目标优化问题(MOP)分解为多个单目标优化子问题,并同时优化这些子问题。这种方法的核心思想是通过引入权重向量或参考点,将多目标问题转化为多个标量优化问题,每个子问题都关注于原始问题的一个特定方面或视角。这样可…...

conntrack iptables 安全组

centos 安装yum install conntrack-tools 1. conntrack状态 NEW: 新建连接&#xff08;第一次包&#xff09;。 ESTABLISHED: 已建立连接&#xff0c;正在传输数据。 RELATED: 与已有连接相关的连接&#xff0c;如 FTP 数据连接。 INVALID: 无效连接&#xff0c;无法识别或不…...

stringRedisTemplate.execute执行lua脚本

stringRedisTemplate.execute执行lua脚本 1. 引入必要依赖 确保项目中已经引入了Spring Data Redis相关依赖&#xff0c;例如在 Maven 项目中&#xff0c;一般会有如下依赖&#xff08;版本号根据实际情况调整&#xff09;&#xff1a; <dependency><groupId>or…...

HDFS异构存储和存储策略

一、HDFS异构存储类型 1.1 冷、热、温、冻数据 通常&#xff0c;公司或者组织总是有相当多的历史数据占用昂贵的存储空间。典型的数据使用模式是新传入的数据被应用程序大量使用&#xff0c;从而该数据被标记为"热"数据。随着时间的推移&#xff0c;存储的数据每周…...

生成idea ui风格界面代码

创建一个类似 IntelliJ IDEA 的用户界面&#xff08;UI&#xff09;涉及多个组件和复杂的布局设计。为了简化这个过程&#xff0c;我们可以使用 **Java Swing** 或 **JavaFX** 来实现一个基本的 IDE 界面&#xff0c;模仿 IntelliJ IDEA 的主要布局元素&#xff0c;如菜单栏、工…...

嵌入式C语言:二维数组

目录 一、二维数组的定义 二、内存布局 2.1. 内存布局特点 2.2. 内存布局示例 2.2.1. 数组元素地址 2.2.2. 内存布局图&#xff08;简化表示&#xff09; 2.3. 初始化对内存布局的影响 三、访问二维数组元素 3.1. 常规下标访问方式 3.2. 通过指针访问 3.2.1. 指向数…...

【机器学习:四、多输入变量的回归问题】

多输入变量的回归问题 1. 多元线性回归概述 1.1 单变量线性回归与多变量线性回归的概念区分 单变量线性回归&#xff1a;用于预测一个因变量&#xff08;输出变量&#xff09;与单一自变量&#xff08;输入变量&#xff09;之间的线性关系。模型形式为&#xff1a; y θ 0 …...

JVM实战—OOM的定位和解决

1.如何对系统的OOM异常进行监控和报警 (1)最佳的解决方案 最佳的OOM监控方案就是&#xff1a;建立一套监控平台&#xff0c;比如搭建Zabbix、Open-Falcon之类的监控平台。如果有监控平台&#xff0c;就可以接入系统异常的监控和报警&#xff0c;可以设置当系统出现OOM异常&…...

iOS 本地新项目上传git仓库,并使用sourceTree管理

此文记录的场景描述&#xff1a; iOS前期开发时&#xff0c;在本地创建项目&#xff0c;直至开发一段时间&#xff0c;初期编码及框架已完善后&#xff0c;才拿到git仓库的地址。此时需要将本地代码上传到git仓库。 上传至git仓库&#xff0c;可以使用终端&#xff0c;键入命令…...

mysql之基本select语句 运算符 排序分页

1.SQL的分类 DDL:数据定义语言. CREATE ALTER DROP RENAME TRUNCATE DML: 数据操作语言. INSERT DELETE UPDATE SELECT 重中之重 DCL: 数据控制语言. COMMIT ROLLBACK SAVEPOINT GRANT REVOKE 2.SQL语言的规则与规范 1.基本规则 SQL可以在一行或多行,为了提高可…...

如何在 Ubuntu 22.04 上安装 Nagios 服务器教程

简介 在本教程中&#xff0c;我们将解释如何在 Ubuntu 22.04 上安装和配置 Nagios&#xff0c;使用 Apache 作为 Web 服务器&#xff0c;并通过 Let’s Encrypt Certbot 使用 SSL 证书进行保护。 Nagios 是一个强大的监控系统&#xff0c;它可以帮助组织在 IT 基础设施问题影…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

【深度学习新浪潮】什么是credit assignment problem?

Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...

Vue3中的computer和watch

computed的写法 在页面中 <div>{{ calcNumber }}</div>script中 写法1 常用 import { computed, ref } from vue; let price ref(100);const priceAdd () > { //函数方法 price 1price.value ; }//计算属性 let calcNumber computed(() > {return ${p…...

java高级——高阶函数、如何定义一个函数式接口类似stream流的filter

java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用&#xff08;Math::max&#xff09; 2 函数接口…...