欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【算法基础】需要排序的最短子数组长度

程序员文章站 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;
	}
}