面试经典 150 题 ---- 合并两个有序数组
面试经典 150 题 ---- 合并两个有序数组
- 合并两个有序数组
- 方法一:直接合并后排序
- 方法二:双指针
- 方法三:逆向双指针
合并两个有序数组
方法一:直接合并后排序
这种方法最简单,直接将 nums2
的数组放到 nums1
数组的尾部,然后对 nums1
进行排序即可
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {for (int i = 0; i < n; i ++ ) {nums1[i + m] = nums2[i];}Arrays.sort(nums1);}
}
时间复杂度: O((m + n)log(m + n))
数组长度为 m + n,快排的时间复杂度为 O((m + n)log(m + n))
空间复杂度: O((m + n)log(m + n))
数组长度为 m + n,快排的时间复杂度为 O((m + n)log(m + n))
方法二:双指针
方法一没有使用到数组已经被排序的性质。利用这一性质,我们可以使用双指针方法。将两个数组看作队列,每次从数组的头部取出一个比较小的值放到结果中。
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 = 0, p2 = 0;int[] sorted = new int[m + n];int cur = 0;while (p1 < m || p2 < n) {if (p1 == m) {sorted[cur] = nums2[p2++];} else if (p2 == n) {sorted[cur] = nums1[p1++];} else if (nums1[p1] < nums2[p2]) {sorted[cur] = nums1[p1++];} else {sorted[cur] = nums2[p2++];}cur ++ ;}for (int i = 0; i < m + n; i ++ ) {nums1[i] = sorted[i];}}
}
时间复杂度: O(m + n)
指针单调移动,最多移动 m + n 次,因此时间复杂度为 O(m + n)
空间复杂度: O(m + n)
需要建立长度为 m + n 的中间数组
方法三:逆向双指针
方法二需要使用临时变量,是因为直接合并到 nums1
中,nums1
中的元素可能会在取出之前被覆盖。那么如何直接避免覆盖 nums1
中的元素呢?可以使用双指针从后往前遍历,每次取两者之中的比较大者放进 nums1
的最后面。
为什么从后往前,将大的元素放入到
nums1
中就不会出现覆盖元素的情况呢?
可以这样想象。如果是将nums2
中的元素放入了nums1
中,那么此时nums1
的元素肯定不会被覆盖,如果是将nums1
中的元素放入了nums1
的后半部分,nums1
的前半部分就肯定会出现一个空位,从而保证全部元素都可以放进去且不会发生覆盖。
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int p1 = m - 1, p2 = n - 1;int cur = nums1.length - 1;while(p1 >= 0 || p2 >= 0) {if (p1 == -1) {nums1[cur -- ] = nums2[p2 -- ];} else if (p2 == -1) {nums1[cur -- ] = nums1[p1 -- ];} else if (nums1[p1] > nums2[p2]) {nums1[cur -- ] = nums1[p1 -- ];} else {nums1[cur -- ] = nums2[p2 -- ];}}}
}
时间复杂度: O(m + n)
指针单调移动,最多移动 m + n 次,因此时间复杂度为 O(m + n)
空间复杂度: O(m + n)
直接对 nums1
原地修改,不需要额外的空间
相关文章:
面试经典 150 题 ---- 合并两个有序数组
面试经典 150 题 ---- 合并两个有序数组 合并两个有序数组方法一:直接合并后排序方法二:双指针方法三:逆向双指针 合并两个有序数组 方法一:直接合并后排序 这种方法最简单,直接将 nums2 的数组放到 nums1 数组的尾部…...

防火墙在企业园区出口安全方案中的应用(ENSP实现)
拓扑图 需求: 1、企业出口网关设备必须具备较高的可靠性,为了避免单点故障,要求两台设备形成双机热备状态。当一台设备发生故障时,另一台设备会接替其工作,不会影响业务正常运行。 2、企业从两个ISP租用了两条链路&…...

单片机学习笔记---矩阵键盘密码锁
目录 一,设置密码按键 1.设置密码区域 2.设置输入的数字左移 3.设置记录按键的次数 二,设置确认键 1.密码正确时显示OK 2.密码错误时显示ERR 3.密码错误恢复初始状态重输 三,设置取消键 学了这么久,迫不及待想要做一个密…...

8-小程序数据promise化、共享、分包
小程序API Promise化 wx.requet 官网入口 默认情况下,小程序官方异步API都是基于回调函数实现的 wx.request({method: , url: , data: {},header: {content-type: application/json // 默认值},success (res) {console.log(res.data)},fail () {},complete () { }…...

[HTML]Web前端开发技术18(HTML5、CSS3、JavaScript )HTML5 基础与CSS3 应用——喵喵画网页
希望你开心,希望你健康,希望你幸福,希望你点赞! 最后的最后,关注喵,关注喵,关注喵,佬佬会看到更多有趣的博客哦!!! 喵喵喵,你对我真的…...

Threejs 展示——obj 格式模型导入
文章目录 需求分析1. HTML版本2. Vue 版本 需求 导入obj 格式的模型数据 分析 .obj:Wavefront OBJ 格式,是一种广泛使用的三维模型文件格式。预览 .obj格式文件的软件可点此下载需要准备两种格式的数据,如下所示 1. HTML版本 html <!…...

深入浅出 diffusion(3):pytorch 实现 diffusion 中的 U-Net
导入python包 import mathimport torch import torch.nn as nn import torch.nn.functional as F silu激活函数 class SiLU(nn.Module): # SiLU激活函数staticmethoddef forward(x):return x * torch.sigmoid(x) 归一化设置 def get_norm(norm, num_channels, num_groups)…...

C#使用RabbitMQ-2_详解工作队列模式
简介 🍀RabbitMQ中的工作队列模式是指将任务分配给多个消费者并行处理。在工作队列模式中,生产者将任务发送到RabbitMQ交换器,然后交换器将任务路由到一个或多个队列。消费者从队列中获取任务并进行处理。处理完成后,消费者可以向…...

Day37 56合并区间 738单调递增的数字 968监控二叉树
56 合并区间 给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: intervals [[1,3],[2,6],[8,10],[15,18]]输出: [[1,6],[8,10],[15,18]]解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. class Solution { public:vector<vector<int>>…...

【Android】在WSA安卓子系统中进行新实验性功能试用与抓包(2311.4.5.0)
前言 在根据几篇22和23的WSA抓包文章进行尝试时遇到了问题,同时发现新版Wsa的一些实验性功能能优化抓包配置时的一些步骤,因而写下此篇以作记录。 Wsa版本:2311.40000.5.0 本文出现的项目: MagiskOnWSALocal MagiskTrustUserCer…...
【服务器】服务器的管理口和网口
服务器通常会有两种不同类型的网络接口,即管理口(Management Port)和网口(Ethernet Port),它们的作用和用途不同。 一、管理口 管理口通常是用于服务器管理的网络接口,也被称为外带网卡或带外接…...
一个小例子,演示函数指针
结构体里经常看到函数指针的写法,函数指针其实就是函数的名字。但是结构体里你要是直接把一个函数摆上去,那就变成成员变量,就会发生混乱 1. 函数指针 #include <unistd.h> #include <stdio.h>struct Kiwia{void (*func)(int )…...

python12-Python的字符串之使用input获取用户输入
input()函数用于向用户生成一条提示,然后获取用户输入的内容。由于input0函数总会将用户输入的内容放入字符串中,因此用户可以输入任何内容,input()函数总是返回一个字符串。例如如下程序。 # !/usr/bin/env python# -*- coding: utf-8 -*-# @Time : 2024/01# @Author : Lao…...

【代码随想录-数组】移除元素
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老导航 檀越剑指大厂系列:全面总结 jav…...
springboot事务管理
/*spring事务管理注解:Transactional位置:业务(service)层的方法上、类上、接口上作用:将当前方法交给spring进行事务管理,方法执行前,开启事务:成功执行完毕,提交事务:出现常,回滚事务需要在配置文件是加上开启spring事务yml文件…...

数据结构——链式二叉树(2)
目录 🍁一、二叉树的销毁 🍁二、在二叉树中查找某个数,并返回该结点 🍁三、LeetCode——检查两棵二叉树是否相等 🌕(一)、题目链接:100. 相同的树 - 力扣(LeetCode&a…...

spring-boot-starter-validation常用注解
文章目录 一、使用二、常用注解三、Valid or Validated ?四、分组校验1. 分组校验的基本概念2. 定义验证组3. 应用分组到模型4. 在控制器中使用分组5. 总结 一、使用 要使用这些注解,首先确保在你的 Spring Boot 应用的 pom.xml 文件中添加了 spring-bo…...

AF700 NHS 酯,AF 700 Succinimidyl Ester,一种明亮且具有光稳定性的近红外染料
AF700 NHS 酯,AF 700 Succinimidyl Ester,一种明亮且具有光稳定性的近红外染料,AF700-NHS-酯,具有水溶性和 pH 值不敏感性 您好,欢迎来到新研之家 文章关键词:AF700 NHS 酯,AF 700 Succinimid…...

C#常见内存泄漏
背景 在开发中由于对语言特性不了解或经验不足或疏忽,往往会造成一些低级bug。而内存泄漏就是最常见的一个,这个问题在测试过程中,因为操作频次低,而不能完全被暴露出来;而在正式使用时,由于使用次数增加&…...
Xmind安装到指定目录
Xmind安装到指定目录 默认情况下安装包自动引导安装在C盘(注册表默认位置) T1:修改注册表,比较麻烦 T2:安装时命令行指定安装位置,快捷省事 1)下载安装包(exe可执行文件) 2)安装…...

大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...

2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能
1. 开发环境准备 安装DevEco Studio 3.1: 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK 项目配置: // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...