[leetcode刷题]面试经典150题之1合并两个有序数组(简单)

接下来开始刷面试经典150题,计划在24年结束之前刷完。将会分按算法系统刷题和学习,会介绍解题思路和所涉及的知识算法等。

题目 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。

注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。

解决思路:

为了在原地进行合并并保持有序,我们可以使用双指针法从后向前合并,这样可以避免覆盖 nums1 的有效部分。

思路详细说明:

  1. 双指针法

    • 我们使用两个指针分别指向 nums1nums2 的末尾。
    • 第一个指针 i 指向 nums1 的最后一个有效元素(即 m-1),第二个指针 j 指向 nums2 的最后一个元素(即 n-1)。
    • 第三个指针 k 指向 nums1 的末尾位置(即 m + n - 1),这是我们放置合并结果的地方。
  2. 从后往前比较元素

    • 我们从两个数组的末尾开始,比较 nums1[i]nums2[j] 的大小。较大的那个元素放在 nums1[k] 的位置,并且相应地移动指针 ij
    • 如果 nums1[i]nums2[j] 大,就将 nums1[i] 放到 nums1[k],然后将 ik 向前移动。否则,将 nums2[j] 放到 nums1[k],并移动 jk
  3. 处理剩余元素

    • 如果 nums2 中还有剩余元素没有被处理完,那么我们直接将剩余的元素复制到 nums1 的前面,因为 nums1 的前面已经有序了。
    • 如果 nums1 剩下的元素没被处理完(这通常已经是有序的),可以不用动。

代码

class Solution:def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:i=m-1j=n-1k=m+n-1while i>=0 and j>=0:if nums1[i]>nums2[j]:nums1[k]=nums1[i]i-=1else:nums1[k]=nums2[j]j-=1k-=1while j>=0:nums1[k] = nums2[j]j -= 1k -= 1

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

9月26日云技术研讨会 | SOA整车EE架构开发流程及工具实施方案

面向服务的架构(Service Oriented Architecture, SOA)实施需要复杂的基础技术作为支撑,伴随着整车硬件资源的集中化、车载以太网等高速通信技术在车内的部署,将在未来一段时间内成为行业技术研究和市场布局的热点。 近年来&#x…

使用Webpack创建vue脚手架并搭建路由---详解

1.使用 vue 库 vue 是一个非常好用的 javascript 库,现在已经发行了 vue 3,我们可以直接导入使用库文件,也可以使用单文件(SFC)的形式,直接使用库文件会简单一点,我们先来试一下吧。 1.1安装 v…

JdbcTemplate常用方法一览AG网页参数绑定与数据寻址实操

JdbcTemplate是Spring框架中的一个重要组件,主要用于简化JDBC数据库操作。它提供了许多常用的方法,如查询、插入、更新、删除等。本文将介绍JdbcTemplate的常用方法及其使用方式,以及参数绑定和删除数据的方法。 一、JdbcTemplate常用方法 查…

24/9/19 算法笔记 kaggle BankChurn数据分类

题目是要预测银行里什么样的客户会流失,流失的概率是多少 我这边先展示一下我写的二分类的算法 import numpy as np import pandas as pd import matplotlib.pyplot as plt from sklearn.model_selection import train_test_split from sklearn.linear_model impo…

金砖软件测试赛项之Jmeter如何录制脚本!

一、简介 Apache JMeter 是一款开源的性能测试工具,用于测试各种服务的负载能力,包括Web应用、数据库、FTP服务器等。它可以模拟多种用户行为,生成负载以评估系统的性能和稳定性。 JMeter 的主要特点: 图形用户界面:…

Stable Diffusion绘画 | ControlNet应用-IP-Adapter:一致性角色就这么简单

IP-Adapter 更新了全新的模型—FaceID plus V2 版本,同时还支持 SDXL 模型。 FaceID plus V2 版本的优点: 解决任务一致性 一张图生成相似角色 下载地址:https://huggingface.co/h94/IP-Adapter-FaceID/tree/main 其中,两个 Lora文…

AIGC时代!AI的“iPhone时刻”与投资机遇

AIGC时代!AI的“iPhone时刻”与投资机遇 前言AI的“iPhone时刻”与投资机遇 前言 AIGC,也就是人工智能生成内容,它就像是一股汹涌的浪潮,席卷了整个科技世界。它的出现,让我们看到了人工智能的无限潜力,也…

基于协同过滤算法+PHP的新闻推荐系统

作者:计算机学姐 开发技术:SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等,“文末源码”。 专栏推荐:前后端分离项目源码、SpringBoot项目源码、SSM项目源码 系统展示 【2025最新】基于协同过滤算法PHPMySQL的新…

【STM32 HAL库】OLED显示模块

【STM32 HAL库】OLED显示模块 前言理论OLED基本参数OLED基本驱动原理OLED坐标轴 应用CubeMx配置底层函数代码高层封装函数printf显示函数 前言 本文为笔者学习 OLED 的总结,基于keysking的视频内容,如有错误,欢迎指正 理论 OLED基本参数 …

react + antDesign封装图片预览组件(支持多张图片)

需求场景:最近在开发后台系统时经常遇到图片预览问题,如果一个一个的引用antDesign的图片预览组件就有点繁琐了,于是在antDesign图片预览组件的基础上二次封装了一下,避免重复无用代码的出现 效果 公共预览组件代码 import React…

【machine learning-十-grading descent梯度下降实现】

grading descent 梯度下降参数更新方法 --导数和学习率 从导数项直观理解梯度下降 grading descent 算法就是更新参数,今天来学习下如何更新w和b 梯度下降 还是以线性回归的均方差损失函数如下为例: 损失函数的可视化图如下 : 横轴和纵轴分…

影刀RPA实战:网页爬虫之苦瓜书籍数据

书籍常常被视为心灵的慰藉,因为它们能够在不同的层面上为人们提供支持和安慰。 1. 书籍对我们的重要性 书籍是人类知识的载体,也是智慧的结晶。它们不仅是学习的工具,更是人类心灵的慰藉。在忙碌的生活中,书籍能够提供知识、启发…

魅思CMS getOrderStatus SQL注入漏洞复现

0x01 漏洞描述: 魅思是一款集成了视频管理、用户管理、手机端应用封装等功能的综合性视频管理系统。该系统不仅以其强大的视频管理功能、灵活的用户管理机制、便捷的手机端应用封装功能以及高安全性和现代化的界面设计,成为了市场上备受关注的视频管理系…

技术美术百人计划 | 《4.5 DOF景深算法》笔记

1. 景深定义 景深(Depth of Field,DOF),是指在摄影机镜头或其他成像器前沿能够取得清晰图像的成像所测定的被摄物体前后距离范围。镜头光圈、镜头焦距、及焦平面到拍摄物的距离是影响景深的重要因素。在聚焦完成后,焦点…

监控IDS和IPS增强网络安全性

入侵检测系统(IDS)和入侵防御系统(IPS)是当今使用的最复杂的网络安全设备之一,它们检查网络数据包并阻止可疑数据包,并提醒管理员有关攻击企图的信息。 在当今威胁不断变化的网络环境中,防火墙…

TopoDOT2024.1注册机 道路自动化提取 雷达点云数据

TopoDOT2024.1是一套成熟的点云数据处理及应用系统,全面具备点云数据的存储管理、精度检核、特征自动提取、智能分析、高效建模、成果输出等应用功能。TopoDOT在LiDAR数据应用领域有着多年的实战经验,用户在实际项目中长期使用,尤其在交通领域…

iOS 巨魔神器,Geranium 天竺葵:6大功能,个个都解决痛点

嘿,这是黑猫。如果你装了巨魔,却只知道安装第三方APP,那就是暴殄天物。巨魔的价值不仅是应用侧载,还有强大的玩机工具生态——这也是我花费大量时间,去制作巨魔精选IPA合集的原因。 通过巨魔商店安装的APP&#xff0c…

初学者的鸿蒙多线程并发之 TaskPool 踩坑之旅

1. 背景 目标群体:鸿蒙初学者 版本:HarmonyOS 3.1/4.0 背景:鸿蒙 App 的全局路由管理功能,需要在 App 启动时初始化对 raw 下的相关配置文件进行读取、解析并缓存。App 启动时涉及到了大量模块的初始化,好多模块都涉…

智能绘画Midjourney AIGC在设计领域中的应用

科技的进步,人工智能(AI)正以前所未有的方式渗透进各个领域,尤其是在艺术创作,尤其是绘画。Midjourney作为AI绘画技术的代表,其AIGC(Artificial Intelligence for Generative Content&#xff0…

python SQLAlchemy 数据库连接池

文章目录 前言python SQLAlchemy 数据库连接池1. 安装2. 创建数据库引擎3. 新建表,增删改查demo 前言 如果您觉得有用的话,记得给博主点个赞,评论,收藏一键三连啊,写作不易啊^ _ ^。   而且听说点赞的人每天的运气都…