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

面试经典 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 题 ---- 合并两个有序数组 合并两个有序数组方法一&#xff1a;直接合并后排序方法二&#xff1a;双指针方法三&#xff1a;逆向双指针 合并两个有序数组 方法一&#xff1a;直接合并后排序 这种方法最简单&#xff0c;直接将 nums2 的数组放到 nums1 数组的尾部…...

防火墙在企业园区出口安全方案中的应用(ENSP实现)

拓扑图 需求&#xff1a; 1、企业出口网关设备必须具备较高的可靠性&#xff0c;为了避免单点故障&#xff0c;要求两台设备形成双机热备状态。当一台设备发生故障时&#xff0c;另一台设备会接替其工作&#xff0c;不会影响业务正常运行。 2、企业从两个ISP租用了两条链路&…...

单片机学习笔记---矩阵键盘密码锁

目录 一&#xff0c;设置密码按键 1.设置密码区域 2.设置输入的数字左移 3.设置记录按键的次数 二&#xff0c;设置确认键 1.密码正确时显示OK 2.密码错误时显示ERR 3.密码错误恢复初始状态重输 三&#xff0c;设置取消键 学了这么久&#xff0c;迫不及待想要做一个密…...

8-小程序数据promise化、共享、分包

小程序API Promise化 wx.requet 官网入口 默认情况下&#xff0c;小程序官方异步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 应用——喵喵画网页

希望你开心&#xff0c;希望你健康&#xff0c;希望你幸福&#xff0c;希望你点赞&#xff01; 最后的最后&#xff0c;关注喵&#xff0c;关注喵&#xff0c;关注喵&#xff0c;佬佬会看到更多有趣的博客哦&#xff01;&#xff01;&#xff01; 喵喵喵&#xff0c;你对我真的…...

Threejs 展示——obj 格式模型导入

文章目录 需求分析1. HTML版本2. Vue 版本 需求 导入obj 格式的模型数据 分析 .obj&#xff1a;Wavefront OBJ 格式&#xff0c;是一种广泛使用的三维模型文件格式。预览 .obj格式文件的软件可点此下载需要准备两种格式的数据&#xff0c;如下所示 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_详解工作队列模式

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

Day37 56合并区间 738单调递增的数字 968监控二叉树

56 合并区间 给出一个区间的集合&#xff0c;请合并所有重叠的区间。 示例 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抓包文章进行尝试时遇到了问题&#xff0c;同时发现新版Wsa的一些实验性功能能优化抓包配置时的一些步骤&#xff0c;因而写下此篇以作记录。 Wsa版本&#xff1a;2311.40000.5.0 本文出现的项目&#xff1a; MagiskOnWSALocal MagiskTrustUserCer…...

【服务器】服务器的管理口和网口

服务器通常会有两种不同类型的网络接口&#xff0c;即管理口&#xff08;Management Port&#xff09;和网口&#xff08;Ethernet Port&#xff09;&#xff0c;它们的作用和用途不同。 一、管理口 管理口通常是用于服务器管理的网络接口&#xff0c;也被称为外带网卡或带外接…...

一个小例子,演示函数指针

结构体里经常看到函数指针的写法&#xff0c;函数指针其实就是函数的名字。但是结构体里你要是直接把一个函数摆上去&#xff0c;那就变成成员变量&#xff0c;就会发生混乱 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进行事务管理&#xff0c;方法执行前&#xff0c;开启事务:成功执行完毕&#xff0c;提交事务:出现常&#xff0c;回滚事务需要在配置文件是加上开启spring事务yml文件…...

数据结构——链式二叉树(2)

目录 &#x1f341;一、二叉树的销毁 &#x1f341;二、在二叉树中查找某个数&#xff0c;并返回该结点 &#x1f341;三、LeetCode——检查两棵二叉树是否相等 &#x1f315;&#xff08;一&#xff09;、题目链接&#xff1a;100. 相同的树 - 力扣&#xff08;LeetCode&a…...

spring-boot-starter-validation常用注解

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

AF700 NHS 酯,AF 700 Succinimidyl Ester,一种明亮且具有光稳定性的近红外染料

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

C#常见内存泄漏

背景 在开发中由于对语言特性不了解或经验不足或疏忽&#xff0c;往往会造成一些低级bug。而内存泄漏就是最常见的一个&#xff0c;这个问题在测试过程中&#xff0c;因为操作频次低&#xff0c;而不能完全被暴露出来&#xff1b;而在正式使用时&#xff0c;由于使用次数增加&…...

Xmind安装到指定目录

Xmind安装到指定目录 默认情况下安装包自动引导安装在C盘&#xff08;注册表默认位置&#xff09; T1:修改注册表&#xff0c;比较麻烦 T2:安装时命令行指定安装位置&#xff0c;快捷省事 1&#xff09;下载安装包&#xff08;exe可执行文件&#xff09; 2&#xff09;安装…...

大话软工笔记—需求分析概述

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

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 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 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&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...