LeetCode题练习与总结:最短无序连续子数组--581
一、题目描述
给你一个整数数组 nums
,你需要找出一个 连续子数组 ,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组,并输出它的长度。
示例 1:
输入:nums = [2,6,4,8,10,9,15] 输出:5 解释:你只需要对 [6, 4, 8, 10, 9] 进行升序排序,那么整个表都会变为升序排序。
示例 2:
输入:nums = [1,2,3,4] 输出:0
示例 3:
输入:nums = [1] 输出:0
提示:
1 <= nums.length <= 10^4
-10^5 <= nums[i] <= 10^5
二、解题思路
- 首先复制原数组,并对复制后的数组进行排序。
- 然后分别从数组的两端开始比较原数组与排序后的数组。
- 找到第一个不同的元素位置,即为需要排序的子数组的起始位置。
- 找到最后一个不同的元素位置,即为需要排序的子数组的结束位置。
- 计算这两个位置之间的距离,即为需要排序的最短子数组的长度。
三、具体代码
import java.util.Arrays;class Solution {public int findUnsortedSubarray(int[] nums) {// 复制原数组并进行排序int[] sortedNums = nums.clone();Arrays.sort(sortedNums);// 初始化子数组的起始和结束位置int start = 0, end = nums.length - 1;// 从两端开始比较原数组与排序后的数组while (start < nums.length && nums[start] == sortedNums[start]) {start++;}while (end > start && nums[end] == sortedNums[end]) {end--;}// 计算需要排序的子数组的长度return end - start + 1;}
}
这段代码首先复制了原数组并进行排序,然后从数组的两端开始比较,直到找到第一个和最后一个不同的元素,最后计算这两个位置之间的距离,即为需要排序的最短子数组的长度。如果整个数组已经是有序的,那么返回的长度将是0。
四、时间复杂度和空间复杂度
1. 时间复杂度
- 复制原数组:这个操作的时间复杂度是 O(n),其中 n 是数组的长度。
- 对数组进行排序:使用的是
Arrays.sort()
方法,该方法在大多数情况下使用的是双轴快速排序,其平均时间复杂度是 O(n log n)。 - 比较原数组与排序后的数组:最坏情况下需要遍历整个数组,因此时间复杂度是 O(n)。
综上所述,总的时间复杂度是 O(n) + O(n log n) + O(n),简化后是 O(n log n),因为排序操作通常是最大的时间开销。
2. 空间复杂度
- 复制原数组:这个操作的空间复杂度是 O(n),因为需要额外的空间来存储一个与原数组大小相同的数组。
因此,总的空间复杂度是 O(n)。
五、总结知识点
-
数组操作:
- 使用
clone()
方法来复制一个数组。这是一个浅拷贝,适用于基本数据类型。 - 使用
Arrays.sort()
方法对数组进行排序。这个方法内部使用的是双轴快速排序算法。
- 使用
-
循环结构:
- 使用
while
循环来遍历数组元素,以找到需要排序的子数组的起始和结束位置。
- 使用
-
数组索引与边界条件:
- 使用数组索引来访问数组元素。
- 使用边界条件来防止数组越界。例如,
start < nums.length
和end > start
。
-
逻辑判断:
- 使用
==
运算符来比较数组元素是否相等。 - 使用
&&
运算符来进行逻辑与运算,确保在满足特定条件时才执行循环体中的代码。
- 使用
-
算法逻辑:
- 通过比较原数组与排序后的数组,确定需要排序的子数组的边界。
- 计算子数组长度的逻辑:
end - start + 1
。
-
方法定义与返回值:
- 定义了一个
findUnsortedSubarray
方法,它接受一个整数数组作为参数,并返回一个整数,表示需要排序的子数组的长度。
- 定义了一个
-
Java基础语法:
- 类定义(
class
关键字)。 - 方法定义(
public
访问修饰符,返回类型,方法名,参数列表)。 - 变量声明与初始化(
int start = 0, end = nums.length - 1;
)。
- 类定义(
以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。
相关文章:
LeetCode题练习与总结:最短无序连续子数组--581
一、题目描述 给你一个整数数组 nums ,你需要找出一个 连续子数组 ,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。 请你找出符合题意的 最短 子数组,并输出它的长度。 示例 1: 输入:num…...
探秘 TCP TLP:从背景到实现
回家的路上还讨论了个关于 TCP TLP 的问题,闲着无事缕一缕。本文内容参考自 Tail Loss Probe (TLP): An Algorithm for Fast Recovery of Tail Losses 以及 Linux 内核源码。 TLP,先说缘由。自 TCP 引入 Fast retrans 机制就是为了尽力避免 RTO…...

linux学习之网络编程
一、两个模型及其对应关系 OSI七层模型 TCP/IP 四层模型 -------------------------------------------------------------------------- 应用层 表示层 ----> …...
scrol家族 offset家族 client家族学习
Scroll 系列属性 scrollTop & scrollLeft scrollTop: 返回元素的内容已向上滚动的部分的高度。scrollLeft: 返回元素的内容已向左滚动的部分的宽度。 scrollHeight & scrollWidth scrollHeight: 返回元素的实际高度,包括由于溢出而在屏幕上不可见的内容…...
css-background-color(transparent)
1.前言 在 CSS 中,background-color 属性用于设置元素的背景颜色。除了基本的颜色值(如 red、blue 等)和十六进制颜色值(如 #FF0000、#0000FF 等),还有一些特殊的属性值可以用来设置背景颜色。 2.backgrou…...

如何将xps文件转换为txt文件?xps转为pdf,pdf转为txt,提取pdf表格并转为txt
文章目录 xps转txt方法一方法二 pdf转txt整页转txt提取pdf表格,并转为txt 总结另外参考XPS文件转换为TXT文件XPS文件转换为PDF文件PDF文件转换为TXT文件提取PDF表格并转为TXT示例代码(部分) 本文测试代码已上传,路径如下ÿ…...

【Samba】Ubuntu20.04 Windows 共享文件夹
【Samba】Ubuntu20.04 Windows 共享文件夹 前言整体思路检查 Ubuntu 端 和 Windows 网络通信是否正常创建共享文件夹安装并配置 Samba 服务器安装 Samba 服务器创建 Samba 用户编辑 Samba 配置文件重启 Samba 服务器 在 Windows 端 访问 Ubuntu 的共享文件夹 前言 本文基于 Ub…...
gradle和maven的区别以及怎么选择使用它们
目录 区别 1. 配置方式 2. 依赖管理 3. 构建性能 4. 灵活性和扩展性 5. 多项目构建 如何选择使用 选择 Maven 的场景 选择 Gradle 的场景 区别 1. 配置方式 Maven: 使用基于 XML 的 pom.xml 文件进行配置。所有的项目信息、依赖管理、构建插件等都在这个文…...
360大数据面试题及参考答案
数据清理有哪些方法? 数据清理是指发现并纠正数据文件中可识别的错误,包括检查数据一致性,处理无效值和缺失值等。常见的数据清理方法有以下几种: 去重处理:数据中可能存在重复的记录,这不仅会占用存储空间,还可能影响分析结果。通过对比每条记录的关键属性,若所有关键…...
Myeclipse最新版本 C1 2019.4.0
Myeclipse C1 2019.4.0下载地址:链接: https://pan.baidu.com/s/1MbOMLewvAdemoQ4FNfL9pQ 提取码: tmf6 1.1、什么是集成开发环境? ★集成开发环境讲究-站式开发,使用这个工具即可。有提示功能,有自动纠错功能。 ★集成开发环境可以让软件开…...
MySQL 9.2.0 的功能
MySQL 9.2.0 的功能 MySQL 9.2.0 的功能新增、弃用和删除内容如下: 新增功能 权限新增12:引入了CREATE_SPATIAL_REFERENCE_SYSTEM权限,拥有该权限的用户可执行CREATE SPATIAL REFERENCE SYSTEM、CREATE OR REPLACE SPATIAL REFERENCE SYSTEM…...

接口 V2 完善:分布式环境下的 WebSocket 实现与 Token 校验
🎯 本文档详细介绍了如何使用WebSocket协议优化客户端与服务端之间的通信,特别是在处理异步订单创建通知的场景中。通过引入WebSocket代替传统的HTTP请求-响应模式,实现了服务器主动向客户端推送数据的功能,极大地提高了实时性和效…...
微前端架构在前端开发中的实践与挑战
随着单页面应用(SPA)和前端框架如 React、Vue、Angular 的快速发展,现代前端应用的复杂度日益提升。尤其是当应用规模逐渐增大时,单一的代码库往往难以应对不同团队的协作和版本管理问题。为了应对这一挑战,微前端架构…...

【自学嵌入式(6)天气时钟:软硬件准备、串口模块开发】
天气时钟:软硬件准备、串口模块开发 软硬件准备接线及模块划分ESP8266开发板引脚图软件准备 串口模块编写串口介绍Serial库介绍 近期跟着网上一些教学视频,编写了一个天气时钟,本篇及往后数篇都将围绕天气时钟的制作过程展开。本文先解决硬件…...

macbook安装go语言
通过brew来安装go语言 使用brew命令时,一般都会通过brew search看看有哪些版本 brew search go执行后,返回了一堆内容,最下方展示 If you meant "go" specifically: It was migrated from homebrew/cask to homebrew/core. Cas…...
代码随想录算法训练营第三十八天-动态规划-完全背包-322. 零钱兑换
太难了 但听了前面再听这道题感觉递推公式也不是不难理解 动规五部曲 dp[j]代表装满容量为j(也就是目标值)的背包最少物品数量递推公式:dp[j] std::min(dp[j], dp[j - coins[i]] 1)当使用coins[i]这张纸币时,要向前找到容量为…...

小阿卡纳牌
小阿卡纳牌 风:热湿 火:热干 水:冷湿 土:冷干 火风:温度相同,但是湿度不同,二人可能会在短期内十分热情,但是等待热情消退之后,会趋于平淡。 湿度相同、温度不同&#x…...
DDD 和 TDD
领域驱动设计(DDD) DDD 是一种软件开发方法,强调通过与领域专家的密切合作来构建一个反映业务逻辑的模型。其核心思想是将业务逻辑和技术实现紧密结合,以便更好地解决复杂的业务问题。 DDD 的关键概念: 1. 领域模型 …...
Java学习教程,从入门到精通,JDBC插入记录语法及案例(104)
JDBC插入记录语法及案例 一、JDBC插入记录语法 在JDBC中,插入记录主要通过执行SQL的INSERT语句来实现。其基本语法如下: INSERT INTO 表名 (列1, 列2, ..., 列n) VALUES (值1, 值2, ..., 值n);表名:需要插入记录的表的名称。列1, 列2, …,…...

Linux文件基本操作
Linux 的设计哲学 在 Linux 中,一切皆文件! 什么是文件? 文件是具有永久存储性,按特定字节顺序组成的命名数据集 文件可分为:文本文件,二进制文件 文本文件:每个文件存放一个 ASCII 码 存储…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...