当前位置: 首页 > 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封装的图形绘…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

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

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

使用SSE解决获取状态不一致问题

使用SSE解决获取状态不一致问题 1. 问题描述2. SSE介绍2.1 SSE 的工作原理2.2 SSE 的事件格式规范2.3 SSE与其他技术对比2.4 SSE 的优缺点 3. 实战代码 1. 问题描述 目前做的一个功能是上传多个文件&#xff0c;这个上传文件是整体功能的一部分&#xff0c;文件在上传的过程中…...

如何在Windows本机安装Python并确保与Python.NET兼容

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...

加密通信 + 行为分析:运营商行业安全防御体系重构

在数字经济蓬勃发展的时代&#xff0c;运营商作为信息通信网络的核心枢纽&#xff0c;承载着海量用户数据与关键业务传输&#xff0c;其安全防御体系的可靠性直接关乎国家安全、社会稳定与企业发展。随着网络攻击手段的不断升级&#xff0c;传统安全防护体系逐渐暴露出局限性&a…...

怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)

+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...