需要排序的最短子数组长度-Toy模板网

这篇具有很好参考价值的文章主要介绍了需要排序的最短子数组长度。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

需要排序的最短子数组长度

【题目】

给定一个无序数组 arr，求出需要排序的最短子数组长度。
例如：arr = [1,5,3,4,2,6,7]返回 4，因为只有[5,3,4,2]需要排序。

思路：找出一个数组里面的【排序的最短子数组长度】，重点是要排序，所以我们首先重新拷贝一份数组的内容出来，其中一份利用排序算法进行排序，排序之后将两个数组对比发现，对应下标的数据理应一致才是排序后的数组，不相同的地方就是需要排序的子数组，它的长度就是我们要求的。则我们可以找出不相同的最小下标和最大下标，最大下标-最小下标+1就是我们要求的。我们设置两个变量赋初值-1，在循环里找到第一个不相同的下标就赋值给最小下标，之后这个下标不需要再修改，最大下标是每发现有一个不相同的下标就马上重新赋值。

代码：文章来源地址https://www.toymoban.com/news/detail-639382.html

package Test.shuzu;

public class getMinLength {
    public int getMinLen(int[] arr){

        if(arr==null||arr.length<2)
        {
            return 0;
        }
        int[] arr1=new int[arr.length];
        System.arraycopy(arr,0,arr1,0,arr.length);

        for(int i=0;i<arr.length;i++)
        {
            int min=i;
            for(int j=i+1;j<arr.length;j++)
            {
                if(arr[j]<arr[min])
                {
                    min=j;
                }
            }
                if (min != i) {
                int temp = arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
            }
        }
        int min=-1;
        int max=-1;
        for (int i=0 ;i< arr1.length;i++) {
            if(arr1[i]!=arr[i])
            {
                if(min==-1)
                    min=i;
                max=i;
            }

        }
        if(max==-1)
            return 0;
        else
            return max-min+1;
    }
}