88. 合并两个有序数组 (Swift版本)

题目

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

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

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

提示

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -109 <= nums1[i], nums2[j] <= 109

解答

方法1: 合并后使用系统方法 sort() (最简单, 最直接)

Show Code
class Solution {func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {// range operator (区间运算符/区间操作符)for idx in 0..<n {nums1[m + idx] = nums2[idx]}// 闭包表达式的简短方式nums1.sort(by: <)}
}
复杂度分析
  • 时间复杂度:O((m+n)log(m+n))

    排序序列长度为 m+n,套用 sort 方法的时间复杂度即可,平均情况为 O((m+n)log⁡(m+n))

  • 空间复杂度: O(m+n)

    排序序列长度为 m+n,套用sort 方法的空间复杂度即可,平均情况为 O(m+n)

Swift 的内置排序算法 sort()Swift5 之后采用了 TimSort,相较于之前的 Introsortstability, 什么是 stability?它是_一种排序后维持相等元素的原始顺序的能力_, 关于 Swift 中 sort() 的 stability, 可以参考 Is sort() stable in Swift 5?

TimSort 是一种混合算法 ,包含插入排序O(n^2)归并排序O(nlogn), 因为 插入 和 归并 都是 stability, 所以 TimSort 也是

TimSort 核心原理是 切割 + 合并, 具体实现可参考 TimSort

TimSort 的平均时间复杂度为O(nlogn) ,最好情况O(n) ,最差情况O(nlogn) 。 空间复杂度O(n) ,是一个稳定的排序算法。 自该算法被发明以来,已被Python、Java、Android 平台和GNU Octave 用作默认排序算法。

执行用时&内存消耗

在这里插入图片描述

方法2: 双指针

方法一没有利用数组 nums1 与 nums2 已经被排序的性质。为了利用这一性质,我们可以使用双指针方法。这一方法将两个数组看作队列,每次从两个数组头部取出比较小的数字放到结果中。

Show code
    func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {var p1 = 0, p2 = 0var sorted = [Int]()while p1 < m || p2 < n {if p1 == m {sorted.append(nums2[p2])p2 += 1// 很重要, 没有则会向下执行, 最终Crash -> Fatal error: Index out of rangecontinue}if p2 == n {sorted.append(nums1[p1])p1 += 1// 很重要, 没有则会向下执行, 最终Crash -> Fatal error: Index out of rangecontinue}if nums1[p1] < nums2[p2] {sorted.append(nums1[p1])p1 += 1} else {sorted.append(nums2[p2])p2 += 1}}for idx in 0..<(m+n) {nums1[idx] = sorted[idx]}}
复杂度分析
  • 时间复杂度: O(m + n)

    指针移动单调递增,最多移动 m+n 次,因此时间复杂度为 O(m+n)

  • 空间复杂度: O(m + n)

    需要建立长度为 m+n 的中间数组 sorted

方法3: 逆向双指针

方法二中,之所以要使用临时变量,是因为如果直接合并到数组 nums1 中,nums1 中的元素可能会在取出之前被覆盖。那么如何直接避免覆盖 nums1 中的元素呢?观察可知,nums1 的后半部分是空的,可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历,每次取两者之中的较大者放进 nums1 的最后面。

严格来说,在此遍历过程中的任意一个时刻,nums1 数组中有 m−p1−1 个元素被放入 nums1 的后半部,nums2 数组中有 n−p2−1 个元素被放入 nums1 的后半部,而在指针 p1 的后面,nums1 数组有 m+n−p1−1 个位置。由于

m+n−p1−1≥m−p1−1+n−p2−1

等价于

p2≥−1

永远成立,因此 p1 后面的位置永远足够容纳被插入的元素,不会产生 p1 的元素被覆盖的情况。

Show code
    func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {var p1 = m - 1, p2 = n - 1var tail = m + n - 1while p1 > -1 || p2 > -1 {if p1 == -1 {nums1[tail] = nums2[p2]tail -= 1p2 -= 1continue}if p2 == -1 {nums1[tail] = nums1[p1]tail -= 1p1 -= 1continue}if nums1[p1] > nums2[p2] {nums1[tail] = nums1[p1]p1 -= 1tail -= 1} else {nums1[tail] = nums2[p2]p2 -= 1tail -= 1}}}
复杂度分析
  • 时间复杂度: O(m + n)

    指针移动单调递减,最多移动 m+n 次,因此时间复杂度为 O(m+n)

  • 空间复杂度: O(1)

    直接对数组 nums1 原地修改,不需要额外空间

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

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

相关文章

Python数据分析-5

1.时间序列 2.pandas重采样 重采样&#xff1a;指的是将时间序列从一个频率转化为另一个频率进行处理的过程&#xff0c;将高频率数据转化为低频率数据为降采样&#xff0c;低频率转 化为高频率为升采样。 统计出911数据中不同月份电话次数的变化情况&#xff1a…

PlantUML Integration 编写短信服务类图

PlantUML Integration 写一个类图&#xff0c;主要功能为 1、编写一个serviceSms短信服务类&#xff1b; 2、需要用到短信的地方统一调用基建层的服务即可&#xff1b; 3、可以随意切换、增加短信厂商&#xff0c;不需要更改场景代码&#xff0c;只需要更改application.yml 里面…

边缘计算与物联网的核心 —— 低功耗芯片

一、低功耗芯片 在边缘计算与物联网&#xff08;IoT&#xff09;中&#xff0c;低功耗芯片扮演了至关重要的角色&#xff0c;主要体现在以下几个方面&#xff1a; 延长设备寿命&#xff1a;物联网设备通常需要部署在难以更换电池或不方便进行频繁维护的环境中&#xff0c;比如…

学习使用postman软件上传文件发起api接口请求

学习使用postman软件上传文件发起api接口请求 设置headers头信息设置body 设置headers头信息 如图设置&#xff1a; KEY&#xff1a;Content-Type VALUE&#xff1a;multipart/form-data 设置body 设置需要上传的key对应的类型为File&#xff0c;上传类型 设置需要上传的文件…

物联网技术助力智慧城市转型升级:智能、高效、可持续

目录 一、物联网技术概述及其在智慧城市中的应用 二、物联网技术助力智慧城市转型升级的路径 1、提升城市基础设施智能化水平 2、推动公共服务智能化升级 3、促进城市治理现代化 三、物联网技术助力智慧城市转型升级的成效与展望 1、成效显著 2、展望未来 四、物联网技…

import gdal 报错

1.下载gdal https://www.lfd.uci.edu/~gohlke/pythonlibs/#gdal 2.安装正确版本 &#xff08;1&#xff09;查看python版本 python -v我的版本Python 3.7.9 建议下载 GDAL-3.4.2-cp37-cp37m-win_amd64.whl &#xff08;2&#xff09;放到Scripts文件夹下 执行 pip install GD…

CVPR2024 | 大核卷积新高度101x101,美团提出PeLK

https://arxiv.org/pdf/2403.07589.pdf 本文概述 最近&#xff0c;一些大核卷积网络以吸引人的性能和效率进行了反击。然而&#xff0c;考虑到卷积的平方复杂度&#xff0c;扩大内核会带来大量的参数&#xff0c;而大量的参数会引发严重的优化问题。由于这些问题&#xff0c;当…

网络编程套接字(4)——Java套接字(TCP协议)

目录 一、Java流套接字通信模型 二、TCP流套接字编程 1、ServerSocket ServerSocket构造方法&#xff1a; ServerSocket方法: 2、Socket Socket构造方法&#xff1a; Socket方法&#xff1a; 三、代码示例&#xff1a;回显服务器 1、服务器代码 代码解析 2、客户端…

机械女生,双非本985硕,目前学了C 基础知识,转嵌入式还是java更好?

作为单片机项目开发的卖课佬&#xff0c;个人建议&#xff0c;先转嵌入式单片机开发方向&#xff0c;哈哈。 java我也学过&#xff0c;还学过oracle、mysql数据库&#xff0c;只是当时没做笔记&#xff0c;找不好充分的装逼证据了。 从实习通过业余时间&#xff0c;学到快正式毕…

AI 大模型赋能手机影像,小米14 Ultra 让真实有层次

2月22日&#xff0c;小米龙年第一场重磅发布会&#xff0c;正式发布专业影像旗舰小米14 Ultra。 此前小米发布的两代 Ultra&#xff0c;在不同维度&#xff0c;引领了移动影像行业的走向。最新的小米14 Ultra 在定义的时候&#xff0c;我们反复在思考&#xff1a;怎么才能把移动…

HBase安装,配置,启动,检查

目录: 一、HBase安装&#xff0c;配置 1、下载HBase安装包 2、解压&#xff0c;配置环境变量并激活 3、hbase 配置 4、将hadoop和zookeeper的配置文件创建软连接放在hbase配置目录 5、配置 regionserver 和 backup-master 二、HBase启动与关闭&#xff0c;安装检验 1、启动关闭…

吴恩达深度学习笔记:神经网络的编程基础2.9-2.14

目录 第一门课&#xff1a;神经网络和深度学习 (Neural Networks and Deep Learning)第二周&#xff1a;神经网络的编程基础 (Basics of Neural Network programming)2.9 逻辑回归中的梯度下降&#xff08;Logistic Regression Gradient Descent&#xff09; 第一门课&#xff…

蓝牙耳机链接电脑莫名奇妙关机问题(QQ浏览器)

蓝牙耳机连接电脑听歌的时候&#xff0c;如果听歌软件是暴风影音&#xff0c;或者其它播放器&#xff0c;蓝牙不会自动关机&#xff0c;但如果是QQ浏览器&#xff0c;蓝牙耳机经常莫名其妙的关机&#xff0c;时间间隔忽长忽短&#xff0c;没有规律&#xff0c;解决办法就是重启…

【C++ 设计模式】简单工厂模式

文章目录 前言一、简单工厂模式是什么&#xff1f;二、实现原理三、UML类图四、简单工厂模式具体代码总结 前言 在软件开发中&#xff0c;设计模式是解决特定问题的可复用解决方案。其中&#xff0c;简单工厂模式是一种创建型设计模式&#xff0c;旨在封装对象的创建过程&…

使用耳机壳UV树脂制作私模定制耳塞的价格如何呢?

耳机壳UV树脂制作私模定制耳塞的价格因多个因素而异&#xff0c;如材料、工艺、设计、定制复杂度等。 根据我目前所了解到的信息&#xff0c;使用UV树脂制作私模定制耳塞的价格可能在数百元至数千元不等。具体价格还需根据用户的需求和预算进行综合考虑。 如需获取更准确的报…

MySQL order by 语句执行流程

全字段排序 假设这个表的部分定义是这样的&#xff1a; CREATE TABLE t (id int(11) NOT NULL,city varchar(16) NOT NULL,name varchar(16) NOT NULL,age int(11) NOT NULL,addr varchar(128) DEFAULT NULL,PRIMARY KEY (id),KEY city (city) ) ENGINEInnoDB; 有如下 SQL 语…

抖音在线点赞任务发布接单运营平台PHP网站源码

源码简介 抖音在线点赞任务发布接单运营平台PHP网站源码 多个支付通道分级会员制度 介绍&#xff1a; 1、三级代理裂变&#xff0c;静态返佣/动态返佣均可设置。&#xff08;烧伤制度&#xff09;。 2、邀请二维码接入防红跳转。 3、自动机器人做任务&#xff0c;任务时间…

STM32CubeIDE基础学习-STM32CubeIDE软件新增工程文件夹

STM32CubeIDE基础学习-STM32CubeIDE软件新增工程文件夹 文章目录 STM32CubeIDE基础学习-STM32CubeIDE软件新增工程文件夹前言第1章 添加文件夹第2章 添加文件路径2.1 相对路径方法2.2 绝对路径方法 总结 前言 在编程的过程中&#xff0c;如果需要在原有的工程基础上新增其它的…

微信小程序-day01

文章目录 前言微信小程序介绍 一、为什么要学习微信小程序?二、微信小程序的历史创建开发环境1.注册账号2.获取APPID 三、下载微信开发者工具1.创建微信小程序项目2.填写相关信息3.项目创建成功 四、小程序目录结构项目的主体组成结构 总结 前言 微信小程序介绍 微信小程序&…

【OceanBase诊断调优 】 —— 合并问题如何排查?

最近总结一些诊断OCeanBase的一些经验&#xff0c;出一个【OceanBase诊断调优】专题&#xff0c;也欢迎大家贡献自己的诊断OceanBase的方法。 1. 前言 OceanBase 数据库的存储引擎基于 LSM-Tree 架构&#xff0c;将数据分为静态基线数据&#xff08;放在 SSTable 中&#xff…