【算法基础】需要排序的最短子数组长度
程序员文章站
2024-03-16 12:46:46
...
给定一个无序数组arr,求出需要排序的子数组长度
* 思路:
* 先从右到左遍历数组
* min : 出现的最小元素
* noMinIndex : 出现无序(cur > min)时的位置
* 再从左到右遍历数组
* max : 出现的最大元素
* noMaxIndex : 出现无序(cur < max)时的位置
* 用noMaxIndex - noMinIndex得到结果
源代码
package com.javakk.ex;
/**
* @Time 2018年8月30日 下午2:30:06
* @Title { 需要排序的最短子数组长度 }
* @Desc { 给定一个无序数组arr,求出需要排序的子数组长度 }
* @Email [email protected]
* @Author JavaKK
*/
public class Ex10 {
public static void main(String[] args) {
int[] arr = { 1, 5, 3, 4, 2, 6, 7 };
int n = getMinSortLength(arr);
System.out.println(n);
}
/**
* 思路:
* 先从右到左遍历数组
* min : 出现的最小元素
* noMinIndex : 出现无序(cur > min)时的位置
* 再从左到右遍历数组
* max : 出现的最大元素
* noMaxIndex : 出现无序(cur < max)时的位置
* 用noMaxIndex - noMinIndex得到结果
* @param arr
* @return
*/
private static int getMinSortLength(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) {
// 出现无序的情况
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) {
// 出现无序的情况
noMaxIndex = i;
} else {
max = Math.max(max, arr[i]);
}
}
return noMaxIndex - noMinIndex + 1;
}
}
上一篇: 两个排序数组的中位数
下一篇: LeetCode 两个排序数组的中位数