需要排序的最短子数组长度
程序员文章站
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;
}
上一篇: Manacher 算法
推荐阅读
-
需要排序的最短子数组长度
-
python计算迷宫最短路径长度(即二维数组最左上角到最右下角的最小路径长度)
-
需要排序的最短子数组长度
-
【算法基础】需要排序的最短子数组长度
-
需要排序的最短子数组长度
-
牛客网刷题java之在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。输入这样的一个二维数组和一个整数,判断数组中是否含有该整数
-
在两个长度相等的排序数组中找到上中位数
-
在两个长度相等的排序数组中找到上中位数
-
在两个长度相等的排序数组中找到中位数
-
最短无序连续子数组(在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...中找到第 n 个数字。)