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

思路

首先从左往右遍历,然后设定一个Max,如果遍历的过程中array[i]大于Max,则置换Max,若小于Max,则指定 k 记录该位置。
然后再从右往左遍历,设定一个Min,在遍历的过程中array[i]小于Min,则置换Min,若大于Min,则指定 j 记录该位置。
于是 j~~k之间的就是需要排序的。
如上例,Max首先是1,然后遍历
Max=1,array[i]=1,置换Max,Max=1
Max=1,array[i]=5,置换Max,Max=5
Max=5,array[i]=3,k指向3,k=2,此时5~~3之间需要排序
Max=5,array[i]=4,k指向4,k=3,此时5~~4之间需要排序
依次类推,k最终指向2.
从右往左遍历的结果类似。

public class ShortNeedSortNum {

  public static void main(String[] args) {

  int[] arr = {4,5,3,2,1,6,7};

   System.out.println(getMinlength(arr));

  }

  public static int getMinlength(int[] arr){

     if(arr==null||arr.length==0){

       return 0;

    }

    int length = arr.length;

     int min = arr[length-1];

           int noMinIndex = -1;

     for(int i=length-2; i>=0; i–){

     if(arr[i]>min){

       noMinIndex = i;

     }else{

       min = arr[i];    

     }

    }

    if(noMinIndex==-1){

     return 0;

    }

     int max = arr[0];

          int noMaxIndex = -1;

     for(int i=1; i<length; i++){

      if(arr[i]<max){

       noMaxIndex = i;

     }else{

          max = arr[i];

        }

      }

     return noMaxIndex-noMinIndex+1;

    }

}

IT文库 » 给定一个无序数组arr,求出需要排序的最短子数组长度。例如: arr = [1,5,3,4,2,6,7] 返回4,因为只有[5,3,4,2]需要排序。
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址