首页 > 代码库 > 给定一个无序数组arr,求出需要排序的最短子数组长度。例如: arr = [1,5,3,4,2,6,7] 返回4,因为只有[5,3,4,2]需要排序。
给定一个无序数组arr,求出需要排序的最短子数组长度。例如: arr = [1,5,3,4,2,6,7] 返回4,因为只有[5,3,4,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;
}
}
给定一个无序数组arr,求出需要排序的最短子数组长度。例如: arr = [1,5,3,4,2,6,7] 返回4,因为只有[5,3,4,2]需要排序。