C语言重构【581】最短无序连续子数组

约定不等于承诺〃 2022-12-19 06:13 129阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
    
    你找到的子数组应是最短的，请输出它的长度。
    
    示例 1:
    
    输入: [2, 6, 4, 8, 10, 9, 15]
    输出: 5
    解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
    说明 :
    
    输入的数组长度范围在 [1, 10,000]。
    输入的数组可能包含重复元素 ，所以升序的意思是<=。

#### 方案： ####

*  [参考思路，非常巧妙][Link 1]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70_pic_center]
 *  我们可以假设把这个数组分成三段，左段和右段是标准的升序数组，中段数组虽是无序的，但满足最小值大于左段的最大值，最大值小于右段的最小值。
 *  那么我们目标就很明确了，找中段的左右边界，我们分别定义为begin 和 end;  
    分两头开始遍历:
    
     *  从左到右维护一个最大值max,在进入右段之前，那么遍历到的nums\[i\]都是小于max的，我们要求的end就是遍历中最后一个小于max元素的位置；
     *  同理，从右到左维护一个最小值min，在进入左段之前，那么遍历到的nums\[i\]也都是大于min的，要求的begin也就是最后一个大于min元素的位置。

class Solution { 
    public:
        int findUnsortedSubarray(vector<int>& nums) { 
            //初始化
            int len = nums.size();
            int min = nums[len-1];
            int max = nums[0];//无序区间的最大数
            int begin=0,end=-1;
            //遍历
            for(int i =0;i<len;i++){ 
                //若当前遍历数比max小，说明end边界需要后移（即这个数在无区间）
                if(nums[i]<max){ 
                    end = i;
                }else{ 
                    //找到更大的无序区间的数
                    max = nums[i];
                }
                //如果当前值比最小值要大，则说明区间有序，则可以将begin边界往后移，
                if(nums[len-i-1]>min){ 
                    begin = len-i-1;
                }else{ 
                    min = nums[len-i-1];
                }
            }
            return end-begin+1;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode
[Link 1]: https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/si-lu-qing-xi-ming-liao-kan-bu-dong-bu-cun-zai-de-/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5bXVhbXVh_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/bd7861b3931343609bed14f0156fd724.png