当前位置 博文首页 > Inmaturity_7的博客：算法练习帖--20--数组部分排序(Java)
给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。注意：n-m尽量最小，也就是说，找出符合条件的最短序列。函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。
（题目来源：力扣（LeetCode））
示例：
输入： [1,2,4,7,10,11,7,12,6,7,16,18,19]
输出： [3,9]
提示：
0 <= len(array) <= 1000000
1. 双指针法
public static int[] subSort(int[] array) {
int length=array.length;
if(array==null||array.length<=1){
return new int[]{-1,-1};
}
//第一个指针
int first=-1;
//第二个指针
int last=-1;
//从左往右寻找最大值
int max=Integer.MIN_VALUE;
//从右往左寻找最小值
int min=Integer.MAX_VALUE;
for (int i = 0; i < length; i++) {
//从左看，如果一直升序则不需要排序
//当有值小于左侧序列最大值的时候，说明这个数必须纳入到需要排序的范围
if(array[i]<max){
last=i;
}else{
max=Math.max(max,array[i]);
}
//从右看，如果一直降序则不需要排序
//当有值大于最小值的时候，说明这个数必须纳入到需要排序的范围
if(array[length-i-1]>min){
first=length-i-1;
}else{
min=Math.min(min,array[length-i-1]);
}
}
//循环完找到两个下标first,last
//没找到的话,说明整个序列都是有序的
return new int[]{first,last};
}
2. 整体排序+比较
//记录两个数组不同区间的下标
int first=-1;
int last=-1;
//是否找到第一个下标的标志
boolean fFlag=false;
//是否找到第二个下标的标志
boolean lFlag=false;
for (int i = 0; i < length; i++) {
if(!fFlag&&array[i]!=sortArray[i]){
first=i;
fFlag=true;
}
if(!lFlag&&array[length-i-1]!=sortArray[length-i-1]){
last=length-i-1;
lFlag=true;
}
}
3. 更多解法
cs