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

最短无序连续子数组

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

题意整理

给定一个整数数组，找出一个连续子数组，将这个子数组升序排列后整个数组都变为升序数组。
求满足条件的最短的连续子数组的长度。

方法一（排序）

1.解题思路

首先定义一个新数组arr，将原数组的值复制到新数组。
对原数组nums进行排序。
从前往后，找到第一个不相等的元素位置，记为子数组的起点。从后往前，找到第一个不相等的元素位置，记为子数组的终点。计算起点、终点距离，即可知道对应子数组的长度。

图解展示： alt

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int findUnsortedSubarray (int[] nums) {
        //数组长度
        int n=nums.length;
        //复制原数组到arr数组
        int[] arr=Arrays.copyOf(nums,n);
        //对应原数组nums进行排序
        Arrays.sort(nums);
        //start记录最短无序连续子数组的起点。end记录对应的终点
        int start=-1,end=-1;
        for(int i=0;i<n;i++){
            //如果不相等，将i标记为起点，并结束循环
            if(arr[i]!=nums[i]){
                start=i;
                break;
            }
        }
        for(int i=n-1;i>=0;i--){
            //如果不相等，将i标记为终点，并结束循环
            if(arr[i]!=nums[i]){
                end=i;
                break;
            }
        }
        //如果所有元素都相等，直接返回0，否则返回对应长度
        return (start==-1&&end==-1)?0:end-start+1;
    }
}

3.复杂度分析

时间复杂度：需要对数组进行排序，以及遍历整个数组，排序的时间复杂度为 $O (n l o g_{2} n)$ ，遍历的时间复杂度为 $O (n)$ ，所以时间复杂度是 $O (n l o g_{2} n)$ 。
空间复杂度：需要额外大小为n的arr数组，所以空间复杂度为 $O (n)$ 。

方法二（贪心）

1.解题思路

首先找到使得数组无序的对应位置最小值，以及使得数组无序的对应位置最大值，然后找第一个大于最小值的位置，必定是子数组的起点，而前面的数都小于这个最小值，接着从后往前找第一个小于最大值的位置，必定是子数组的终点，而后面的数都大于这个最大值。所以起点、终点之间一定是最短无序的连续子数组。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int findUnsortedSubarray (int[] nums) {
        //数组长度
        int n=nums.length;
        //startNum记录最短无序连续子数组的最小值，endNum记录对应的最大值
        int startNum=100001,endNum=-1;
        //start记录最短无序连续子数组的起点。end记录对应的终点
        int start=-1,end=-1;
        for(int i=1;i<n;i++){
            if(nums[i]<nums[i-1]){
                startNum=Math.min(startNum,nums[i]);
            }
        }
        for(int i=0;i<n;i++){
            //如果大于startNum，说明是子数组的起点
            if(nums[i]>startNum){
                start=i;
                break;
            }
        }
        for(int i=n-2;i>=0;i--){
            if(nums[i]>nums[i+1]){
                endNum=Math.max(endNum,nums[i]);
            }
        }
        for(int i=n-1;i>=0;i--){
            //如果小于endNum，说明是子数组的终点
            if(nums[i]<endNum){
                end=i;
                break;
            }
        }
        //如果所有元素都相等，直接返回0，否则返回对应长度
        return (start==-1&&end==-1)?0:end-start+1;
    }
}