欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【时间复杂度优化】LeetCode 581. Shortest Unsorted Continuous Subarray

程序员文章站 2022-03-07 18:27:55
...

题目描述

【时间复杂度优化】LeetCode 581. Shortest Unsorted Continuous Subarray

知识点

数组

结果

【时间复杂度优化】LeetCode 581. Shortest Unsorted Continuous Subarray

实现

码前思考

对于这个题目,可以先将原数组pre排序得到后数组after,然后得到两个数组不相同区域的左边界和右边界即可~(话说,这个排序会不会有点过于暴力。。。)

代码实现

//直接数组排序开干?为啥准确率这么低
class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> sortedNums = nums;
        sort(sortedNums.begin(),sortedNums.end());

        int start=0;
        int end;

        while(start < nums.size() && nums[start] == sortedNums[start]){
            start++;
        }

        end=start;

        for(int i=start+1;i<nums.size();i++){
            if(nums[i] != sortedNums[i]){
                end = i;
            }
        }

        if(end == start){
            return 0;
        }else{
            return end-start+1;
        }
    }
};

码后反思

  1. 第一次提交的时候又忘记 检查数组下标越界的问题 了!!!看来有时还是不要装逼比较好,虽然代码繁琐点,但是能够保证正确啊。
    输入测试用例:1,2,3,4,如果不写下面这个判断条件,就会数组越界!
    【时间复杂度优化】LeetCode 581. Shortest Unsorted Continuous Subarray

优化

下面是使用O(n)O(n)时间复杂度的解法:

同时从前往后和从后往前遍历,分别得到要排序数组的右边界和左边界;

寻找右边界:
从前往后遍历的过程中,用max记录遍历过的最大值,如果max大于当前的nums[i],说明nums[i]的位置不正确,属于需要排序的数组,因此将右边界更新为i,然后更新max;这样最终可以找到需要排序的数组的右边界,右边界之后的元素都大于max;

寻找左边界:
从后往前遍历的过程中,用min记录遍历过的最小值,如果min小于当前的nums[j],说明nums[j]的位置不正确,应该属于需要排序的数组,因此将左边界更新为j,然后更新min;这样最终可以找到需要排序的数组的左边界,左边界之前的元素都小于min;

(从前往后遍历和从后往前遍历两个过程可以分两次循环完成,也可以放一起完成,这样的话就有:j=len-i-1)

其实这个思想很好理解:

  • 右边界的定义:右边界的左边一定存在一个比右边界大的数,导致它不配在右边界这个位置;
  • 左边界的定义:左边界的右边一定存在一个比左边界小的数,导致它不配在左边界这个位置。
    主要突破点还是在于理解左右边界的含义吧~这才是牛逼的人吧,把概念真正弄懂!!!

网络的代码如下:

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int len = nums.length;
        int max = nums[0];
        int min = nums[len-1];
        int l = 0, r = -1;
        for(int i=0;i<len;i++){
            if(max>nums[i]){
                r = i;
            }else{
                max = nums[i];
            }
            if(min<nums[len-i-1]){
                l = len-i-1;
            }else{
                min = nums[len-i-1];
            }
        }
        return r-l+1;
    }
}

作者:zackqf
链接:https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/shi-jian-chao-guo-100de-javajie-fa-by-zackqf/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

相关标签: # 数组