美文网首页
581. 最短无序连续子数组

581. 最短无序连续子数组

作者: 名字是乱打的 | 来源:发表于2021-12-29 00:29 被阅读0次

一 题目:

二 思路:

分析:这个子数组有个特征

  • 子数组前面的数都是升序的,且最后一个数小于子数组里的任意一个数
  • 子数组后面的数都是升序的,且第一个数大于子数组里的任意一个数

因此可以分析出几个思路:
思路1:双指针+排序

  • 我们可以先拷贝个数组对其排序
  • 然后从左到右进行比较,第一个不同的点即为子数组起点
  • 然后从右到左进行比较,第一个不同的点即为子数组终点
    时间复杂度:O(nlogn),空间复杂度:O(n)

思路2:效率更高
同时从前往后和从后往前遍历,分别得到要排序数组的右边界和左边界;

  • 寻找右边界:
    从前往后遍历的过程中,用max记录遍历过的最大值,如果max大于当前的nums[i],说明nums[i]的位置不正确,属于需要排序的数组,因此将右边界更新为i,然后更新max;这样最终可以找到需要排序的数组的右边界,右边界之后的元素都大于max;
  • 寻找左边界:
    从后往前遍历的过程中,用min记录遍历过的最小值,如果min小于当前的nums[j],说明nums[j]的位置不正确,应该属于需要排序的数组,因此将左边界更新为j,然后更新min;这样最终可以找到需要排序的数组的左边界,左边界之前的元素都小于min;
    (从前往后遍历和从后往前遍历两个过程可以分两次循环完成,也可以放一起完成,这样的话就有:j=len-i-1)
    时间复杂度:O(n) ,空间复杂度:O(1)

三 代码:

思路1,双指针+排序

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        //拷贝份
        int[] clone = nums.clone();
        Arrays.sort(clone);

        //子数组左边界
        int left=0;
        //子数组右边届
        int right=nums.length-1;
        while (left<nums.length){
            if (nums[left]==clone[left]){
                left++;
            }else {
                break;
            }
        }

        while (right>=0){
            if (nums[right]==clone[right]){
                right--;
            }else {
                break;
            }
        }
        return right>left?right-left+1:0;
    }
}

思路2:

public int findUnsortedSubarray(int[] nums) {
        int len=nums.length;
        int max=nums[0];
        int min=nums[len-1];
        //这里right定义为-1,是为了避免数组本身有序的情况
        int left=0,right=-1;
        for (int i = 0; i < len; i++) {
            //寻找右边届
            if (max>nums[i]){
                right=i;
            }else {
                max=nums[i];
            }

            //寻找左边界
            if (min<nums[len-1-i]){
                left=len-1-i;
            }else {
                min=nums[len-1-i];
            }
        }
        return right-left+1;
    }

相关文章

  • TOP 96 - 100

    581. 最短无序连续子数组[https://leetcode-cn.com/problems/shortest-...

  • 581. 最短无序连续子数组

    内容 给定一个整数数组,你需要寻找一个连续的子数组,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。 ...

  • 581.最短无序连续子数组

    581. 最短无序连续子数组 难度简单375收藏分享切换为英文关注反馈 给定一个整数数组,你需要寻找一个连续的子数...

  • 581. 最短无序连续子数组

    给定一个整数数组,你需要寻找一个连续的子数组,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。 你找到...

  • 581. 最短无序连续子数组

    解法

  • 581. 最短无序连续子数组

    一 题目: 二 思路: 分析:这个子数组有个特征 子数组前面的数都是升序的,且最后一个数小于子数组里的任意一个数 ...

  • LeetCode 581. 最短无序连续子数组

    题目 给定一个整数数组,你需要寻找一个连续的子数组,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。 ...

  • Leetcode 581. 最短无序连续子数组

    题目描述 给定一个整数数组,你需要寻找一个连续的子数组,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序...

  • LeetCode 刷题总结(8)

    581. 最短无序连续子数组 思路 拷贝把备份排序,然后两个指针,依次从头到尾(i),从尾到头(j)比较排序前后两...

  • 最短无序连续子数组

    题目描述:给定一个整数数组,你需要寻找一个连续的子数组,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序...

网友评论

      本文标题:581. 最短无序连续子数组

      本文链接:https://www.haomeiwen.com/subject/qjbmqrtx.html