题解 | #最短无序连续子数组#

最短无序连续子数组

http://www.nowcoder.com/practice/d17f4abd1d114617b51e951027be312e

题目的主要信息：

给定一个无序数组，找出其中最短的子数组，将这个子数组排序后，整个数组都是升序数组
返回该子数组的长度

方法一：排序比较法

具体做法：

既然要满足将子数组排序后整个数组都是升序数组，我们可以拷贝一份数组进行排序，这样我们就有一份原数组和一份排序后的数组。分别从首尾开始往中间找，分别找到第一个不同的元素，将这之间的子数组排序就是完整的升序数组了，因为两边都一样。因此这个区间的长度就是我们要找的子数组的长度。

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> sorted(nums); //拷贝一份数组
        sort(sorted.begin(), sorted.end()); //对其排序
        int left = 0;
        while (nums[left] == sorted[left]) //从头找到原数组与排序数组第一个不同元素的位置
            left++;
        int right = nums.size() - 1;
        while (nums[right] == sorted[right]) //从尾到头找到原数组与排序数组第一个不同元素的位置
            right--;
        if(right < 0) //全部元素都是有序的
            return 0;
        return right - left + 1; //最短无序区间就是两个不同位置之间
    }
};

复杂度分析：

时间复杂度： $O (n l o g_{2} n)$ ，排序的时间复杂度
空间复杂度： $O (n)$ ，辅助数组拷贝了一份原数组

方法二：一次遍历法

具体做法：

上述方法一中，目标区间左端和右端都是升序排列好的，不用再重排，那意味着左端区间升序，左端的所有元素肯定小于目标区间和右端区间的所有元素，且任意一个数都小于它右边的所有元素，那我们只要找到第一个不满足小于它右边任意一个元素的值就可找到目标区间的起点。同理，目标区间的终点看右端区间就行了。

怎么找这两个端点，在一次遍历中，枚举往后的最大值（从前往后）和最小值（从后往前）就可以了，遇到遇到更大（更小的）的更新最大值（最小值），遇到更小的（更大的）更新区间端点。后续需要检验是否整个数组都为有序的情况。

alt

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int maxn = INT_MIN;
        int minn = INT_MAX; 
        int left = -1;
        int right = -1;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            if(maxn > nums[i]) //更新区间
                right = i;
            else //更新最大值
                maxn = nums[i];
            if(minn < nums[n - i - 1]) //更新区间
                left = n - i - 1;
            else //更新最小值
                minn = nums[n - i - 1];
        }
        return right == -1 ? 0 : right - left + 1; //right到-1就是整个数组都有序
    }
};

复杂度分析：