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

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

二、解题思路

  1. 首先复制原数组,并对复制后的数组进行排序。
  2. 然后分别从数组的两端开始比较原数组与排序后的数组。
  3. 找到第一个不同的元素位置,即为需要排序的子数组的起始位置。
  4. 找到最后一个不同的元素位置,即为需要排序的子数组的结束位置。
  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 &#xff0c;你需要找出一个 连续子数组 &#xff0c;如果对这个子数组进行升序排序&#xff0c;那么整个数组都会变为升序排序。 请你找出符合题意的 最短 子数组&#xff0c;并输出它的长度。 示例 1&#xff1a; 输入&#xff1a;num…...

探秘 TCP TLP:从背景到实现

回家的路上还讨论了个关于 TCP TLP 的问题&#xff0c;闲着无事缕一缕。本文内容参考自 Tail Loss Probe (TLP): An Algorithm for Fast Recovery of Tail Losses 以及 Linux 内核源码。 TLP&#xff0c;先说缘由。自 TCP 引入 Fast retrans 机制就是为了尽力避免 RTO&#xf…...

linux学习之网络编程

一、两个模型及其对应关系 OSI七层模型 TCP/IP 四层模型 -------------------------------------------------------------------------- 应用层 表示层 ----> …...

scrol家族 offset家族 client家族学习

Scroll 系列属性 scrollTop & scrollLeft scrollTop: 返回元素的内容已向上滚动的部分的高度。scrollLeft: 返回元素的内容已向左滚动的部分的宽度。 scrollHeight & scrollWidth scrollHeight: 返回元素的实际高度&#xff0c;包括由于溢出而在屏幕上不可见的内容…...

css-background-color(transparent)

1.前言 在 CSS 中&#xff0c;background-color 属性用于设置元素的背景颜色。除了基本的颜色值&#xff08;如 red、blue 等&#xff09;和十六进制颜色值&#xff08;如 #FF0000、#0000FF 等&#xff09;&#xff0c;还有一些特殊的属性值可以用来设置背景颜色。 2.backgrou…...

如何将xps文件转换为txt文件?xps转为pdf,pdf转为txt,提取pdf表格并转为txt

文章目录 xps转txt方法一方法二 pdf转txt整页转txt提取pdf表格&#xff0c;并转为txt 总结另外参考XPS文件转换为TXT文件XPS文件转换为PDF文件PDF文件转换为TXT文件提取PDF表格并转为TXT示例代码&#xff08;部分&#xff09; 本文测试代码已上传&#xff0c;路径如下&#xff…...

【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&#xff1a; 使用基于 XML 的 pom.xml 文件进行配置。所有的项目信息、依赖管理、构建插件等都在这个文…...

360大数据面试题及参考答案

数据清理有哪些方法? 数据清理是指发现并纠正数据文件中可识别的错误,包括检查数据一致性,处理无效值和缺失值等。常见的数据清理方法有以下几种: 去重处理:数据中可能存在重复的记录,这不仅会占用存储空间,还可能影响分析结果。通过对比每条记录的关键属性,若所有关键…...

Myeclipse最新版本 C1 2019.4.0

Myeclipse C1 2019.4.0下载地址&#xff1a;链接: https://pan.baidu.com/s/1MbOMLewvAdemoQ4FNfL9pQ 提取码: tmf6 1.1、什么是集成开发环境? ★集成开发环境讲究-站式开发&#xff0c;使用这个工具即可。有提示功能&#xff0c;有自动纠错功能。 ★集成开发环境可以让软件开…...

MySQL 9.2.0 的功能

MySQL 9.2.0 的功能 MySQL 9.2.0 的功能新增、弃用和删除内容如下&#xff1a; 新增功能 权限新增12&#xff1a;引入了CREATE_SPATIAL_REFERENCE_SYSTEM权限&#xff0c;拥有该权限的用户可执行CREATE SPATIAL REFERENCE SYSTEM、CREATE OR REPLACE SPATIAL REFERENCE SYSTEM…...

接口 V2 完善:分布式环境下的 WebSocket 实现与 Token 校验

&#x1f3af; 本文档详细介绍了如何使用WebSocket协议优化客户端与服务端之间的通信&#xff0c;特别是在处理异步订单创建通知的场景中。通过引入WebSocket代替传统的HTTP请求-响应模式&#xff0c;实现了服务器主动向客户端推送数据的功能&#xff0c;极大地提高了实时性和效…...

微前端架构在前端开发中的实践与挑战

随着单页面应用&#xff08;SPA&#xff09;和前端框架如 React、Vue、Angular 的快速发展&#xff0c;现代前端应用的复杂度日益提升。尤其是当应用规模逐渐增大时&#xff0c;单一的代码库往往难以应对不同团队的协作和版本管理问题。为了应对这一挑战&#xff0c;微前端架构…...

【自学嵌入式(6)天气时钟:软硬件准备、串口模块开发】

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

macbook安装go语言

通过brew来安装go语言 使用brew命令时&#xff0c;一般都会通过brew search看看有哪些版本 brew search go执行后&#xff0c;返回了一堆内容&#xff0c;最下方展示 If you meant "go" specifically: It was migrated from homebrew/cask to homebrew/core. Cas…...

代码随想录算法训练营第三十八天-动态规划-完全背包-322. 零钱兑换

太难了 但听了前面再听这道题感觉递推公式也不是不难理解 动规五部曲 dp[j]代表装满容量为j&#xff08;也就是目标值&#xff09;的背包最少物品数量递推公式&#xff1a;dp[j] std::min(dp[j], dp[j - coins[i]] 1)当使用coins[i]这张纸币时&#xff0c;要向前找到容量为…...

小阿卡纳牌

小阿卡纳牌 风&#xff1a;热湿 火&#xff1a;热干 水&#xff1a;冷湿 土&#xff1a;冷干 火风&#xff1a;温度相同&#xff0c;但是湿度不同&#xff0c;二人可能会在短期内十分热情&#xff0c;但是等待热情消退之后&#xff0c;会趋于平淡。 湿度相同、温度不同&#x…...

DDD 和 TDD

领域驱动设计&#xff08;DDD&#xff09; DDD 是一种软件开发方法&#xff0c;强调通过与领域专家的密切合作来构建一个反映业务逻辑的模型。其核心思想是将业务逻辑和技术实现紧密结合&#xff0c;以便更好地解决复杂的业务问题。 DDD 的关键概念&#xff1a; 1. 领域模型 …...

Java学习教程,从入门到精通,JDBC插入记录语法及案例(104)

JDBC插入记录语法及案例 一、JDBC插入记录语法 在JDBC中&#xff0c;插入记录主要通过执行SQL的INSERT语句来实现。其基本语法如下&#xff1a; INSERT INTO 表名 (列1, 列2, ..., 列n) VALUES (值1, 值2, ..., 值n);表名&#xff1a;需要插入记录的表的名称。列1, 列2, …,…...

Linux文件基本操作

Linux 的设计哲学 在 Linux 中&#xff0c;一切皆文件&#xff01; 什么是文件&#xff1f; 文件是具有永久存储性&#xff0c;按特定字节顺序组成的命名数据集 文件可分为&#xff1a;文本文件&#xff0c;二进制文件 文本文件&#xff1a;每个文件存放一个 ASCII 码 存储…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...