Leetcode刷题100天—面试题 16.16. 部分排序(排序)—day58

前言：

作者：神的孩子在歌唱

大家好，我叫智

面试题 16.16. 部分排序

难度中等78

给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。注意：n-m尽量最小，也就是说，找出符合条件的最短序列。函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。

示例：

输入： [1,2,4,7,10,11,7,12,6,7,16,18,19]
输出： [3,9]

提示：

• 0 <= len(array) <= 1000000

package 排序;
/*
 * https://leetcode-cn.com/problems/sub-sort-lcci/
 *从左向右遍历，逐渐变大,如果当前元素比它之前的最大的元素小，说明不是升序的，更新n为当前元素索引，继续遍历直到末尾
 *从右向左遍历，逐渐变小，如果当前元素比它之后的最小的元素大，说明不是降序的，更新m为当前元素索引，继续遍历直到开始
 */
public class 面试题_16_16_部分排序 {
    public int[] subSort(int[] array) {
    	int m=-1;
    	int n=-1;
    	int[] res=new int[2];
//    	如果array的长度小于1那么就不需要排序了
    	if (array.length>1) {
	//    	定义最小值和最大值
	    	int max=array[0],min=array[array.length-1];
	//    	定义指针
	    	int left=1,right=array.length-2;
	//    	通过while循环遍历每一个值
	    	while(left<array.length){
	//    		右向左,min获取最小值,比较其左边是否有比他大的值，如果有就赋值下标给m
	    		
	    		if (array[right]>min) {
	    			m=right;
				}else {
					min=array[right];
					
				}
	//    		左向右，max获取最大值，比较其右边是否有比他小的值，如果有就赋值其下标给n
	    		if (array[left]<max) {
	    			n=left;
				}else {
					max=array[left];
				}
	
	    		right--;
	    		left++;
			}
    	}
    	
    	res[0]=m;
    	res[1]=n;
    	return res;
    }
}

转载说明：跟我说明，务必注明来源，附带本人博客连接。