我要招人

去企业版

首页 > 试题广场 >

最短无序连续子数组

[编程题]最短无序连续子数组

热度指数：1909 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个整数数组，你需要找出一个连续子数组，将这个子数组升序排列后整个数组都将是升序数组。

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

数据范围：数组长度满足 $1 \le n \le 10^4 \$ ，数组中的元素满足 $|val| \le 10^5 \$

示例1

输入

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

输出

说明

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

示例2

输入

[1,2,3,5,4]

输出

说明

对 5,4 排序即可得到升序数组

算法知识视频讲解

Java

pein531

排序+双指针

排完序后用双指针比对了一下原始数组，然后找出无序部分的长度

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int findUnsortedSubarray (int[] nums) {
        // write code here
        int n = nums.length;
        int[] rawNums = Arrays.copyOfRange(nums, 0, n);
        Arrays.sort(nums);
        int left = 0, right = n - 1;
        while(left < n && rawNums[left] == nums[left]){
            left++;
        }
        while(right >= 0 && rawNums[right] == nums[right]){
            right--;
        }
        return Math.max(right - left + 1, 0);
    }
}

排序的时间复杂度为O(nlogn)，后面双指针的时间复杂度为O(n)，整体的时间复杂度为O(nlogn)。拷贝了原始数组，所以额外空间复杂度为O(n)。

利用单调性

如果某一个数nums[i]满足大于等于左边的最大值，小于等于右边的最小值，这个数在数组中就是不需要移动位置的。因此可以定出如下的算法流程：

从左往右遍历，如果nums[i]始终是nums[0:i]的最大值，就表示目前为止还是升序。如果碰到了不是最大值的情况，就记录位置，当前遇到了乱序。
从右往左遍历，如果nums[i]始终是nums[i:n-1]的最小值，就表示目前为止还是升序。如果碰到了不是最小值的情况，就记录位置，当前遇到了乱序。

而我们通过下标变换可以一遍循环就完成以上两步，根据步骤1能够得到无序的右边界，根据步骤2可以得到无序的左边界，进一步可以求得无序的长度。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        int leftMax = nums[0], rightMin = nums[n - 1], l = -1, r = -2;
        for(int i = 1; i < n; i++){
            leftMax = max(leftMax, nums[i]);                // nums[0:i]的最大值
            rightMin = min(rightMin, nums[n - 1 - i]);      // nums[n-1-i:n-1]的最小值
            if(leftMax != nums[i]){
                r = i;
            }
            if(rightMin != nums[n - 1 - i]){
                l = n - 1 - i;
            }
        }
        return r - l + 1;
    }
};

只遍历了一遍数组，时间复杂度为O(n)。只使用了有限几个变量，空间复杂度为O(1)。

编辑于 2021-12-22 14:41:07 回复(0)

C++

AsherChi

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int findUnsortedSubarray(vector<int>& nums) {
        // write code here
        vector<int> tmp;
        for(int i=0; i<nums.size(); i++)
            tmp.push_back(nums[i]);
        sort(tmp.begin(), tmp.end());
        int left =0, right = 0;
        for(int i=0; i<nums.size(); i++)
        {
            if(nums[i] != tmp[i])
            {
                left = i;
                break;
            }
        }
        for(int i=nums.size()-1; i>=0; i--)
        {
            if(nums[i] != tmp[i])
            {
                right = i;
                break;
            }
        }
        if(left == 0 && right == 0)
            return 0;
        return right - left + 1;
    }
};

发表于 2022-09-05 10:21:23 回复(0)

Python 3

牛客111458759号

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)

小谷围做题家

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)

Java

古月随风

单调栈

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int findUnsortedSubarray (int[] nums) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int start = Integer.MAX_VALUE;
        int end = Integer.MAX_VALUE - 1;
        int curMaxNum = 0;
        for(int i = 0; i < nums.length; i++){
            while(!stack.isEmpty() && nums[stack.peek()] > nums[i]){
                int startTemp = stack.pop();
                start = Math.min(start, startTemp);
            }
            // 更新最大值
            curMaxNum = Math.max(curMaxNum, nums[i]);
            // 如果当前不是最大值，则end 更新到当前位置
            if(curMaxNum != nums[i]){
                end = i;
            }
            stack.push(i);
        }
        return end - start + 1;
    }
}

发表于 2022-09-08 11:37:34 回复(0)

Java

牛客683289936号

暴力
import java.util.*;

public class Solution {
    public int findUnsortedSubarray (int[] nums) {
        // write code here
        int start = -1;
        int end = 0;
        for(int i = 0 ;i<nums.length;i++){
            for(int j = nums.length-1 ;j>i;j--){
                if(nums[j]<=nums[i]){
                    end = j;//最后边的逆序对的终点
                    if(start==-1){
                        start = i;//第一个逆序对的起点
                    }
                    break;
                }
                
            }            
        }
        if(start == -1) return 0;
        return end - start + 1;

    }
}

发表于 2022-03-26 13:38:21 回复(0)

提交观点

问题信息

贪心单调栈双指针

难度：

6条回答 38收藏 1847浏览

通过挑战的用户

查看代码

牛客11145...

2022-10-08 23:39:28
牛客40225...

2022-09-17 12:29:35
Asphyxiay

2022-09-14 02:05:55
牛客用户007

2022-09-13 12:48:52
Ben_澳村留学狗

2022-09-12 23:39:14

最短无序连续子数组

输入

输出

说明

输入

输出

说明

排序+双指针

利用单调性

问题信息

热门推荐

通过挑战的用户

相关试题