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

寻找两个正序数组的中位数

更好的阅读体验,请点击 YinKai 's Blog。

题目:寻找两个正序数组的中位数

给定两个大小分别为 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

提示:

  • nums1.length == m

  • nums2.length == n

  • 0 <= m <= 1000

  • 0 <= n <= 1000

  • 1 <= m + n <= 2000

  • -106 <= nums1[i], nums2[i] <= 106

来源:力扣(LeetCode)

解题思路:
(1)暴力

​ 直接将两个数组合并,然后进行排序,直接算出中位数:

  • 数组长度为奇数,数组的中位数为a[len / 2]
  • 数组长度为偶数,数组的中位数为(a[len / 2] + a[len / 2 - 1]) / 2

​ 这题的时间复杂度的上限在排序,是O((n + m)long(n + m)),显然没有达到题目的要求, 但也勉强可以AC。

​ 代码如下

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {vector<int> res;for (int i = 0; i < nums1.size(); i ++)res.push_back(nums1[i]);for (int i = 0; i < nums2.size(); i ++)res.push_back(nums2[i]);sort(res.begin(), res.end());int len = res.size();if (len & 1) {return res[len / 2];} else {return double((res[len / 2] + res[len / 2 - 1]) / 2.0);}}
};

相关文章:

寻找两个正序数组的中位数

更好的阅读体验&#xff0c;请点击 YinKai s Blog。 题目&#xff1a;寻找两个正序数组的中位数 给定两个大小分别为 m 和 n 的正序&#xff08;从小到大&#xff09;数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 O(log (mn)) 。 …...

探索低代码的潜力、挑战与未来展望

低代码开发作为一种新兴的开发方式&#xff0c;正在逐渐改变着传统的编程模式&#xff0c;低代码使得开发者无需编写大量的代码即可快速构建各种应用程序。然而&#xff0c;低代码也引发了一系列争议&#xff0c;有人称赞其为提升效率的利器&#xff0c;也有人担忧其可能带来的…...

unity 2d 入门 飞翔小鸟 小鸟碰撞 及死亡(九)

1、给地面&#xff0c;柱体这种添加2d盒装碰撞器&#xff0c;小鸟移动碰到就不会动了 2、修改小鸟的脚本&#xff08;脚本命名不规范&#xff0c;不要在意&#xff09; using System.Collections; using System.Collections.Generic; using UnityEngine;public class Fly : Mo…...

实时最优控制(Real-Time Optimal Control)工具

系列文章目录 前言 许多现代控制方法&#xff0c;如模型预测控制&#xff08;model-predictive control&#xff09;&#xff0c;在很大程度上依赖于实时解决优化问题。特别是&#xff0c;高效解决优化控制问题的能力使复杂机器人系统在实现高动态行为&#xff08;highly dyna…...

(env: Windows,mp,1.06.2308310; lib: 3.2.4) uniapp微信小程序

应公司需求&#xff0c;在特定情况下需要修改ip 在开发过程中出现的小插曲 1、第一种情况&#xff1a;重复声明 2、第二种情况&#xff1a; 应官方要求&#xff0c;需要跳转的 tabBar 页面的路径&#xff08;需在 pages.json 的 tabBar 字段定义的页面&#xff09;&#xff0…...

go-zero开发入门-API服务开发示例

接口定义 定义 API 接口文件 接口文件 add.api 的内容如下&#xff1a; syntax "v1"info (title: "API 接口文件示例"desc: "演示如何编写 API 接口文件"author: "一见"date: "2023年12月07日"version: "…...

NVIDIA Jetson NX ubuntu20.04删除多余版本冲突的Boost库

参考Ubuntu16.04 卸载旧版本Boost库并安装新版本 卸载 删除/usr/local/include/boost文件夹&#xff0c;删除/usr/local/lib中和boost有关的文件,以及/usr/local/lib/cmake/中boost的cmake文件 cd /usr/local/lib/ ls | grep boost sudo rm -rf /usr/local/include/boost su…...

【蜗牛到家】获南明电子信息产业引导基金战略投资

智慧社区生活服务平台「蜗牛到家」已于近期获得贵阳南明电子信息产业引导基金、华科明德战略投资。 贵阳南明电子信息产业引导基金属于政府旗下产业引导基金&#xff0c;贵州华科明德基金管理有限公司擅长电子信息产业、高科技产业、城市建设及民生保障领域的投资&#xff0c;双…...

基于ubuntu nc指令实现远程传输文件到嵌入式设备中

背景&#xff1a; 最近在使用nc进行远程文件传输的时候发现在文件传输完成时&#xff0c;没有正确的反馈&#xff0c;而是界面一直停留在传输阶段&#xff0c;加上使用nc传输需要设置一些诸如-l、 -p等参数&#xff0c;于是想将这些参数包裹在sh脚本中&#xff0c;一键执行脚本…...

蓝桥杯 day01 奇怪的数列 特殊日期

奇怪的数列 题目描述 奇怪的数列 从 X 星截获一份电码&#xff0c;是一些数字&#xff0c;如下&#xff1a; 13 1113 3113 132113 1113122113 ⋯⋯ YY 博士经彻夜研究&#xff0c;发现了规律&#xff1a; 第一行的数字随便是什么&#xff0c;以后每一行都是对上一行…...

properties配置和读取

如何配置和读取属性文件 1.属性文件介绍1.1 什么是属性文件1.2属性文件规范1.3 属性文件优缺点 2.属性文件读取4.spring和属性文件4.1利用注解读取4.2配置文件里直接引用 4.属性文件写入5.注意事项5.总结 1.属性文件介绍 1.1 什么是属性文件 Java开发中&#xff0c;我们经常需…...

如何利用人工智能+物联网技术实现自动化设备生产

随着科技的发展与行业竞争的日益激烈&#xff0c;制造业也逐渐走向智能化发展。制造业的改革是利用物联网技术和自动化设备&#xff0c;实现生产线的智能化和自适应生产&#xff0c;优化生产流程&#xff0c;提高生产效率和质量&#xff0c;为企业创造更大的价值。 方案概述 智…...

STM32CubeMx+MATLAB Simulink串口输出实验

STM32CubeMxMATLAB Simulink串口输出实验 &#x1f4cc;《STM32CubeMxMATLAB Simulink点灯程序》&#x1f4cd;相关篇《MATLAB Simulink STM32硬件在环 &#xff08;HIL&#xff09;实现例程测试》&#x1f516;需要的软件支持包&#xff1a;Embedded Coder Support Package fo…...

React中每次渲染都会传入一个新的props.children到子组件?

传入props.children后, 为什么会导致组件的重新渲染&#xff1f; 问题描述 在 react 中, 我想要对组件的渲染进行优化, 遇到了一个非常意思的问题, 当我向一个组件中传入了 props.children 之后, 每次父组件重新渲染都会导致这个组件的重新渲染; 它看起来的表现就像是被memo包…...

Qt 通过命令行编译程序

前言 从服务器拉代码到编译成可执行文件一个脚本解决问题。使用的项目文件见上一个文章 Qt生成动态链接库并使用动态链接库 脚本代码 为了方便易懂这是一个很简单的Qt编译脚本 call E:\vs2015\VC\vcvarsall.bat x86 rmdir /s /q my-project git clone gitgitee.com:wenbai1…...

WireShark监控浏览器登录过程网络请求

软件开发中经常前后端扯皮。一种是用Chrome浏览器的开发者工具 来看网络交互&#xff0c;但是前提是 网络端口的确是通的。 WireShark工作在更低层。 这个工具最大的好处&#xff0c;大家别扯皮&#xff0c;看网络底层的log&#xff0c;到底 你的端口开没开&#xff0c; 数据…...

202301209将RK3399的挖掘机开发板在Android10下设置系统默认为24小时制

202301209将RK3399的挖掘机开发板在Android10下设置系统默认为24小时制 2023/12/9 22:07 应该也可以适用于RK3399的Android12系统 --- a/frameworks/base/packages/SettingsProvider/res/values/defaults.xml b/frameworks/base/packages/SettingsProvider/res/values/default…...

智能优化算法应用:基于法医调查算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于法医调查算法无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于法医调查算法无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.法医调查算法4.实验参数设定5.算法结果6.参考…...

使用MfgTool烧写工具烧写自制系统

一. 简介 本文我们就来学习&#xff0c;如何将我们编译的 uboot&#xff0c;zImage&#xff08;内核镜像&#xff09;&#xff0c;xxx.dtb设备树文件&#xff0c;还有制作的根文件系统&#xff0c;这四个文件烧写到开发板中&#xff0c;最后 开发板能正常启动。 上一篇文章说…...

react中使用react-konva实现画板框选内容

文章目录 一、前言1.1、API文档1.2、Github仓库 二、图形2.1、拖拽draggable2.2、图片Image2.3、变形Transformer 三、实现3.1、依赖3.2、源码3.2.1、KonvaContainer组件3.2.2、use-key-press文件 3.3、效果图 四、最后 一、前言 本文用到的react-konva是基于react封装的图形绘…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...