题目

给定一个无序数组arr，求出需要排序的最短子数组长度。
例如：
arr = [1，5，3，4，2，6，7]
返回4，因为只有[5，3，4，2]需要排序。

思路

TIPS
对于出现子数组,子串等连续的长度，应该想到的是以当前位置结尾的串…
本题对应的是以当前位置结尾的最大最小值

可以排序，然后比较，但是这种方法最多O(log(n))
下面的方面可以达到O(n)

先从前往后遍历，设第一个数为最大值，然后与当前a[i]比较，设置最大移动的坐标，

  • 如果a[i]大，更新最大值
  • 如果a[i]小，则最大移动坐标为i，因为在一个已经排好序的数组中，最大之后面不会出现比他小的数字

同理设置最小值和最小移动的坐标
坐标之差则是需要排序的子数组长度

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public int Find(int []a){
	
	if(a.length == 1){
		return 0;
	}
	//当前需要移动的位置
	int maxIndex = 0;
	//当前最大值
	int max = a[0];
	//从前面遍历，找到最大值和需要移动的位置
	for(int i = 1 ; i < a.length; i++){
		//如果当前值小于最大值，说明要移动，因为最大值的后面不应该出现比他大的
		if(max > a[i]){
			maxIndex = i;
		}else{
			//出现比当前最大值大的，更新最大值
			max = a[i];
		}
	}
	//当前需要移动的位置
	int minIndex = a.length - 1;
	//当前最小值
	int min = a[a.length-1];
	for(int i = a.length-2 ; i >= 0; i--){
		if( min < a[i]){
			minIndex = i;
		}else{
			min = a[i];
		}
	}
	
	return maxIndex - minIndex + 1;
}