首页 > 试题广场 >

最短无序连续子数组

[编程题]最短无序连续子数组
  • 热度指数:2373 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个整数数组,你需要找出一个连续子数组,将这个子数组升序排列后整个数组都将是升序数组。

请你找出满足题设的最短的子数组。

数据范围:数组长度满足 , 数组中的元素满足
示例1

输入

[2,6,4,8,10,9,15]

输出

5

说明

只需对 6,4,8,10,9 排序即可得到升序数组 
示例2

输入

[1,2,3,5,4]

输出

2

说明

对 5,4 排序即可得到升序数组 
class Solution:
    def findUnsortedSubarray(self , nums: List[int]) -> int:
        # write code here
        nums2 = nums[:]
        nums2.sort()     # 思路:复制一个数组,并且按升序排列,这个数组是满足题意后的数组;那么原数组和新数组排列不一样的子数组,就是我们要找的。
        a, b = 0, 0
        if nums2 == nums:
            return 0
        for i in range(len(nums2)):
            if nums[i] != nums2[i]:     # 从左往右数,当原数组和新数组的数字不一样,就是我们要找的子数组的左边界。
                a = i
                break
        for j in range(len(nums2) - 1, -1, -1):
            if nums[j] != nums2[j]:     # 从右往左数,当原数组和新数组的数字不一样,就是我们要找的子数组的右边界。
                b = j
                break
        return (b - a + 1)

发表于 2022-01-03 18:30:00 回复(0)