链接
LeetCode_面试题 16.16. 部分排序
题目
给定一个整数数组，编写一个函数，找出索引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]
思路
找出逆序对: 从左侧向右遍历, 寻找逆序对; 从右侧向左遍历, 寻找逆序对
题解
/*** 时间复杂度: O(n)* [1,2,4,7,10,11,7,12,6,7,16,18,19]* 思路: 找出逆序对* 从左侧向右遍历,寻找逆序对* 从右侧向左遍历,寻找逆序对*/
public int[] subSort(int[] nums) {if(nums.length == 0) return new int[]{-1,-1};int numsLen = nums.length;int max = nums[0];int min = nums[numsLen-1];int lIndex = -1;int rIndex = -1;/*** 为什么在遍历过程中需要更新 max和 min的值?* 因为: 例: [1,5,4,3,2,6,7,6,8]* 如上例, 如果不更新 max, 那么数组[5,8]范围内数据的逆序对将无法检测出来;*/for (int i = 1; i < numsLen; i++) {if(nums[i] >= max){max = nums[i];}else{rIndex = i;}int j = numsLen-1-i;if(nums[j] <= min){min = nums[j];}else{lIndex = j;}}return new int[]{lIndex,rIndex};
}总结
数组为升序, 那么设置并更新max, 如果nums[i+1]小于max, 那么存在逆序对(nums[i],nums[i+1]); 一个数组中只要存在逆序对, 那么该数组一定不是有序的