欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-16 12:54:34
...

【题目】

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

【代码】

public static void main(String[] args) {
        int[] res={1,5,3,4,2,6};
        System.out.println(rank(res));
    } 

    //需要排序的最短子数组长度
    private static int rank(int[] arr) {
        if(arr==null||arr.length==0){
            return 0;
        }
        int min=arr[arr.length-1];//右侧出现过的最小值
        int noMinIndex=-1;
        for(int i=arr.length-2;i!=-1;i--){
            if(arr[i]>min){//min应移到arr[i]左边             noMinIndex=i;
                noMinIndex=i;
            }else{
                min=Math.min(min, arr[i]);
            }
        }
        if(noMinIndex==-1){//从右往左适中不升序
            return 0;
        }
        int max=arr[0];//左侧出现过的最大值
        int noMaxIndex=-1;
        for(int i=1;i<arr.length;i++){
            if(arr[i]<max){//max应移到arr[i]右边
                noMaxIndex=i;
            }else{
                max=Math.max(max, arr[i]);
            }
        }
        return noMaxIndex-noMinIndex+1;
    }