首页 > 试题广场 >

最短无序连续子数组

[编程题]最短无序连续子数组
  • 热度指数: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 排序即可得到升序数组 
package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型
*/
func findUnsortedSubarray( nums []int ) int {
    n:=len(nums)
    if n<2{
        return 0
    }
    max,min:=0,n-1
    ans:=[]int{0,n-1}
    for l,r:=1,n-2;l<n&&r>=0;l,r=l+1,r-1{
        if nums[l]<nums[max]{
            ans[0]=l
        }else{
            max=l
        }
        if nums[r]>nums[min]{
            ans[1]=r
        }else{
            min=r
        }
    }
    if ans[0]<ans[1]{
        return 0
    }
    return ans[0]-ans[1]+1
}

发表于 2023-03-11 17:13:00 回复(0)