【LeetCode】581. 最短的无排序连续子数组

2023-12-27 14:58

本文主要是介绍【LeetCode】581. 最短的无排序连续子数组,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

问题描述

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Note:

  1. Then length of the input array is in range [1, 10,000].
  2. The input array may contain duplicates, so ascending order here means <=.

给定一个整数数组,你需要找到一个连续的子数组,如果只按升序对这个子数组排序,那么整个数组也将按升序排序。
你需要找到最短的子数组并输出它的长度。

注意:
那么输入数组的长度在[1,10,000]范围内。
输入数组可能包含重复项,所以这里升序表示<=。

输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5

 

Python 实现

实现一:排序后再通过比较找出边界。简单粗暴的方法,直接上代码。

class Solution(object):def findUnsortedSubarray(self, nums):""":type nums: List[int]:rtype: int"""length = len(nums)if length <= 1:return 0arr = sorted(nums)length = len(nums)for i in range(length):if arr[i] != nums[i]:breakfor j in range(length, 0, -1):if arr[j-1] != nums[j-1]:breakif j-1 < i:return 0else:return j-i

实现二:寻找左右两个边界。思路和冒泡排序法有点类似,但我们并不是真的进行排序。我们知道,冒泡排序法就是遍历时将前后两个元素进行对比,(假设是升序排序)较大值会被交换到靠后的位置。在这一道题目里,我们不把较大值交换到靠后的位置,而是记录这个最大值,并以之为比较标准,位置靠后且小于该最大值的元素,必然是整个数组排序时需要考虑的部分,也就是我们所要求的最短无排序连续子数组的元素之一,因此我们记录下最靠后的最小值的索引,即为所求子数组的右边界。同理,从右往左遍历,相当于通过冒泡排序法排成降序的形式,我们记录中间出现的最小值作为比较对象,记录最后出现的较大值的索引,即为左边界。

使用上述方法,最多需要遍历两次数组(前后各一次),需要4个变量来记录最大值、最小值、左边界、右边界,因此时间复杂度为 O(n),空间复杂度为 O(1)。

class Solution(object):def findUnsortedSubarray(self, nums):""":type nums: List[int]:rtype: int"""length = len(nums)if length <= 1:return 0left = right = -1maxEdge = nums[0]minEdge = nums[length-1]for i in range(1, length):maxEdge = max(maxEdge, nums[i])if maxEdge > nums[i]:right = iif right == -1:return 0for j in range(length-1, 0, -1):minEdge = min(nums[j-1], minEdge)if minEdge < nums[j-1]:left = j-1return right - left + 1

链接:https://leetcode.com/problems/shortest-unsorted-continuous-subarray/

 

这篇关于【LeetCode】581. 最短的无排序连续子数组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

一文详解Java Stream的sorted自定义排序

《一文详解JavaStream的sorted自定义排序》Javastream中的sorted方法是用于对流中的元素进行排序的方法,它可以接受一个comparator参数,用于指定排序规则,sorte... 目录一、sorted 操作的基础原理二、自定义排序的实现方式1. Comparator 接口的 Lam

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的