581-最短无序连续子数组

马谦马谦马谦

615
文章

17
评论

2019 年 2 月 5 日 12:45:10数据结构和算法评论247字数 967阅读 3 分 13 秒阅读模式

来源：力扣（LeetCode）

链接：581. 最短无序连续子数组，著作权归领扣网络所有。

一、题目描述

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

你找到的子数组应是最短的，请输出它的长度。

示例 1:

输入: [2, 6, 4, 8, 10, 9, 15]

输出: 5

解释: 你只需要对 [6, 4, 8, 10, 9] > 进行升序排序，那么整个表都会变为升序排序。

说明 :

输入的数组长度范围在 [1, 10,000] 。
输入的数组可能包含重复元素，所以升序的意思是<=。

二、题解

官方解析

2.1 排序

算法分析

对数组进行排序，将未排序数组和已排序的数组对比。数组两端朝中间遍历，找到最左边和最右边的不匹配元素，中间的元素就是无序的数组范围。

代码：

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int i, j;

        // 建立辅助数组
        vector<int> sortNums(nums);
        // 排序
        sort(sortNums.begin(), sortNums.end());

        // 找到
        for (i = 0; i < nums.size(); i++) {
            if (nums[i] != sortNums[i]) {
                break;
            }
        }

        // 考虑数组已全部有序的情况
        if (i == nums.size()) {
            return 0;
        }

        for (j = nums.size() - 1; j >= 0; j--) {
            if (nums[j] != sortNums[j]) {
                break;
            }
        }
        
        return j - i + 1;
    }
};

class Solution {

public:

int findUnsortedSubarray(vector<int>& nums) {

int i, j;

// 建立辅助数组

vector<int> sortNums(nums);

// 排序

sort(sortNums.begin(), sortNums.end());

// 找到

for (i = 0; i < nums.size(); i++) {

if (nums[i] != sortNums[i]) {

break;

}

// 考虑数组已全部有序的情况

if (i == nums.size()) {

return 0;

}

for (j = nums.size() - 1; j >= 0; j--) {

if (nums[j] != sortNums[j]) {

break;

}

return j - i + 1;

}

};

581-最短无序连续子数组-图片1

复杂度分析

时间复杂度：O(nlog(n)) 。排序消耗 nlogn 的时间。

空间复杂度：O(n) 。拷贝了一份原数组来进行排序。

2.2 不使用额外空间的用法

以 { 2, 6, 4, 8, 10, 9, 15 }为例，该数组中，最短无序数组是 {6, 4, 8, 10, 9}，可以大概看出的规律是：区间的起点在原数组的第一个降序序列附近（6 和 4 这里），区间的终点在从右到左第一个升序序列附近（10 和 9 这里），因此这里可以认为无序子数组的起点和终点和整个数组的升降点相关。

那是不是说直接从第一个降序点和升序点取子数组就可以了呢？不行，以 { 3, 4, 6, 9, 2, 1 }为例，从左往右的第一个降序点是 9 和 2，从右往左的升序点是 1 和 2，但是失序的数组并不只是这三个元素 {9, 2, 1}，而是 {3, 4, 6, 9, 2, 1}。此时从左往右看，元素 9 左边大于 1 的数组序列也都属于失序数组元素；从右往左看，元素 2 右边所有比 9 小的也属于失序数组。

因此能通过以下算法即便能找出失序数组：

从左往右找到第一个降序点，从这个点开始找到最大的元素 max 。
从右往左找到第一个升序点，从这个点开始找到最小的元素 min 。
从左往右遍历，第一个大于 min 的元素即是失序数组的起点。
从右往左遍历，第一个小于 max 的元素即是失序数组的终点。

代码：

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int max = INT_MIN;
        int min = INT_MAX;

        int i, j;

        // 从左往右，出现降序之后找最大值
        for (i = 1; i < nums.size(); i++) {
            if (nums[i] < nums[i - 1]) {
                min = min < nums[i] ? min : nums[i];
            }
        }
        
        // 从右往左，出现升序之后找最小值
        for (j = nums.size() - 1; j > 0; j--) {
            if (nums[j - 1] > nums[j] ) {
                max = max > nums[j - 1] ? max : nums[j - 1];
            }
        }
        
        // 从左往右找到第一个大于 min 的元素
        for (i = 0; i < nums.size(); i++) {
            if (nums[i] > min)
                break;
        }
        
        // i 遍历到最后一个元素，说明数组已经有序了
        if (i == nums.size())
            return 0;
        
        // 从右往左找到第一个小于 max 的元素
        for (j = nums.size() - 1; j >= 0; j--) {
            if (nums[j] < max)
                break;
        }
        // 计算区间大小
        return j - i + 1;
    }
};