力扣热门100题 - 4.寻找两个正序数组的中位数

力扣热门100题 - 4.寻找两个正序数组的中位数

  • 题目描述:
  • 示例:
  • 提示:
  • 解题思路:
  • 代码:

题目链接:4.寻找两个正序数组的中位数

题目描述:

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例:

输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 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

解题思路:

创建一个 mergeArrays 函数来合并两个有序数组。该函数使用两个指针 mi 和 ni 分别指向数组 nums1 和 nums2 的起始位置,并创建一个新的数组 ans 来存储合并后的结果。

在 mergeArrays 函数中使用循环,比较当前指针位置的值,将较小的值加入到 ans 中,并移动相应的指针,直到其中一个数组的所有元素都被遍历完。

如果其中一个数组已经遍历完(mi == m 或 ni == n),则将另一个数组中剩余的元素直接加入到 ans 中。

最后,返回合并后数组的中位数。如果合并后数组的长度为奇数,则返回中间元素;如果长度为偶数,则返回中间两个元素的平均值。

总体思路就是利用归并排序的思想,将两个有序数组合并成一个有序数组,然后根据合并后数组的长度来找到中位数。

时间复杂度: O(m + n)

合并两个有序数组的时间复杂度:由于该部分的时间复杂度与合并后数组的总长度成正比,因此为 O(m + n),其中 m 和 n 分别为两个输入数组的长度。

计算中位数的时间复杂度:由于只需要常数时间来计算中位数,所以为 O(1)。

因此,总体时间复杂度为 O(m + n)。

代码:

public double findMedianSortedArrays(int[] nums1, int[] nums2) {int[] nums = mergeArrays(nums1, nums2);int len = nums.length;if ((len & 1) == 1) {return nums[len / 2];} else {return (nums[len / 2] + nums[len / 2 - 1]) / 2.0;}}private int[] mergeArrays(int[] nums1, int[] nums2) {int m = nums1.length;int n = nums2.length;int mi = 0, ni = 0;int[] ans = new int[m + n];int ai = 0;while (mi < m && ni < n) {if (nums1[mi] <= nums2[ni]) {ans[ai] = nums1[mi];ai++;mi++;} else {ans[ai] = nums2[ni];ai++;ni++;}}if (mi == m) {while (ni < n) {ans[ai] = nums2[ni];ni++;ai++;}} else {while (mi < m) {ans[ai] = nums1[mi];mi++;ai++;}}return ans;}

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/253141.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

用python编写爬虫,爬取房产信息

题目 报告要求 工程报告链接放在这里 https://download.csdn.net/download/Samature/88816284使用 1.安装jupyter notebook 2.用jupyter notebook打开工程里的ipynb文件&#xff0c;再run all就行 注意事项 可能遇到的bug 暂无&#xff0c;有的话私信我

Verilog刷题笔记20

题目&#xff1a; Case statements in Verilog are nearly equivalent to a sequence of if-elseif-else that compares one expression to a list of others. Its syntax and functionality differs from the switch statement in C. 解题&#xff1a; module top_module ( …

docker自定义镜像并使用

写在前面 本文看下如何自定义镜像。 ik包从这里 下载。 1&#xff1a;自定义带有ik的es镜像 先看下目录结构&#xff1a; /opt/program/mychinese [rootlocalhost mychinese]# ll total 16 -rw-r--r-- 1 root root 1153 Feb 5 04:18 docker-compose.yaml -rw-rw-r-- 1 el…

C语言中的内存函数你知道多少呢?

目录 ​编辑 1. memcpy的使用和模拟实现 1.1函数介绍 ​编辑 1.2函数的使用 1.3模拟实现 2. memmove的使用和模拟实现 2.1函数介绍 2.2函数的使用 2.3模拟实现 3. memset函数的使用 3.1函数介绍 3.2函数的使用 ​编辑 4. memcmp函数的使用 4.1函数介绍 4.2函数…

压力测试工具-Jmeter使用总结

目录 一.前言 二.线程组 三.线程组的组件 四.线程组-HTTP请求 1、JSON提取器 2、XPATH提取器 3、正则表达式提取器 五.线程组-断言 1、响应断言 2、JSON断言 六.创建测试 1.创建线程组 2.配置元件 3.构造HTTP请求 4.添加HTTP请求头 5.添加断言 6.添加查看结果树…

Python 连接 mysql 详解(mysql-connector-python)

文章目录 1 概述1.1 第三方库&#xff1a;mysql-connector-python1.2 可视化工具&#xff1a;navicat1.3 创建测试数据库 2 连接 mysql 数据库2.1 创建一个连接2.2 捕获连接异常2.3 从配置文件中获取连接信息 3 执行 sql 语句3.1 插入、更新、删除3.2 查询 1 概述 1.1 第三方库…

物流自动化移动机器人|HEGERLS三维智能四向穿梭车助力优化企业供应链

智能化仓库/仓储贯穿于物流的各个环节&#xff0c;不局限于存储、输送、分拣、搬运等单一作业环节的自动化&#xff0c;更多的是利用科技手段实现整个物流供应链流程的自动化与智能化&#xff0c;将传统自动化仓储物流各环节进行多维度的有效融合。 例如在数智化物流仓储的建设…

UE4 C++创建摄像机摇臂和相机并且设置Transform

新建MyPawn C类 .h #include "GameFramework/SpringArmComponent.h" //SpringArm组件 #include "Camera/CameraComponent.h" //Camera组件class 工程名称_API AMyPawn : public APawn { //定义组件变量 public:UPROPERTY(VisibleAnywhere, BlueprintRead…

MATLAB计算多边形质心/矩心

前言&#xff1a;不规则四边形的中心 不规则四边形的出心有多种定义&#xff0c;以下是最常见的三种&#xff1a; 1.重心&#xff1a;重心是四边形内部所有顶点连线交点的平均位置。可以通过求解四个顶点坐标的平均值来找到重心。 2.质心&#xff1a;质心是四边形内部所有质点…

【动态规划】【子数组划分】【前缀和】1977. 划分数字的方案数

作者推荐 【动态规划】【状态压缩】【2次选择】【广度搜索】1494. 并行课程 II 本文涉及知识点 动态规划汇总 C算法&#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 LeetCode1977 划分数字的方案数 你写下了若干 正整数 &#xff0c;并将它们…

【Linux笔记】文件系统与软硬链接

一、文件系统概述 1.1、先来聊一聊“磁盘” 在讲解文件系统之前&#xff0c;我觉得有必要先聊一下“磁盘”&#xff0c;因为我觉得如果弄懂了磁盘的存储原理&#xff0c;大家可能更容易理解文件系统是怎么管理数据的&#xff0c;并且理解计算机是怎么将磁盘抽象到文件系统的。…

百度拟将量子实验室捐赠予北京量子院 /一汽解放与华为合作,预计2025年底量产自动驾驶产品 |魔法半周报

我有魔法✨为你劈开信息大海❗ 高效获取AIGC的热门事件&#x1f525;&#xff0c;更新AIGC的最新动态&#xff0c;生成相应的魔法简报&#xff0c;节省阅读时间&#x1f47b; &#x1f525;资讯预览 百度捐赠量子实验室推进量子计算研究&#xff0c;助力人工智能发展 一汽解放…

ionic报错:Cannot read properties of undefined (reading ‘classList‘)

报错信息&#xff1a; [ionic/vue Warning]: The view you are trying to render for path /tabs/tab1 does not have the required <ion-page> component. Transitions and lifecycle methods may not work as expected.See https://ionicframework.com/docs/vue/navig…

【保姆级教程|YOLOv8改进】【5】精度与速度双提升,使用FasterNet替换主干网络

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推…

golang并发安全-sync.Once

什么是sync.Once sync.Once 是 Go 语言中的一种同步原语&#xff0c;用于确保某个操作或函数在并发环境下只被执行一次。它只有一个导出的方法&#xff0c;即 Do&#xff0c;该方法接收一个函数参数。在 Do 方法被调用后&#xff0c;该函数将被执行&#xff0c;而且只会执行一…

C语言第十九弹---指针(三)

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】 指针 1、数组名的理解 2、使用指针访问数组 3、⼀维数组传参的本质 4、冒泡排序 5、二级指针 6、指针数组 7、指针数组模拟二维数组 总结 1、数组名的理解…

flutter go_router 官方路由(一)基本使用

1 项目中添加最新的依赖 go_router: ^13.1.0如下图所示&#xff0c;我当前使用的flutter版本为3.16.0 然后修改应用的入口函数如下&#xff1a; import package:flutter/material.dart; import package:go_router/go_router.dart;void main() {runApp(const MyApp()); }cla…

好看的安全跳转单页html源码

好看的安全跳转单页html源码,效果如下 代码如下&#xff1a; <!DOCTYPE html> <html> <head> <meta charset"UTF-8"> <!--[if IE 8]><style>.ie8 .alert-circle,.ie8 .alert-footer{display:none}.ie8 .alert-box{padding-top:…

使用easyExcel 定义表头 字体 格式 颜色等,定义表内容,合计

HeadStyle 表头样式注解 HeadFontStyle 表头字体样式 HeadStyle(fillPatternType FillPatternTypeEnum.SOLID_FOREGROUND, fillForegroundColor 22) HeadFontStyle(fontHeightInPoints 12) 以下为实现效果

轻型民用无人机驾驶航空器安全操控——理论考试多旋翼部分笔记

今天已经可以在线考取轻型民用无人机驾驶航空器执照了&#xff0c;所以我也在在线观看完视频之后整理了如下的知识点&#xff0c;所有知识点全部来自UOM平台。 目录 航空器知识 &#xff08;1&#xff09;多旋翼民用无人驾驶航空器螺旋桨的作用 &#xff08;2&#x…