部分排序

部分排序

给定一个整数数组，编写一个函数，找出索引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

思路：设三个指针：左边、右边、扫描 ，遵照有序数组的规律，找到左侧最大值和左侧逆序对，一直向右扫描 最终得到最右逆序对；反过来从右向左扫描得到最左逆序对；这两个逆序对中间的范围就是所求答案

时间复杂度：O(n)
空间复杂度：O(1)


class Solution {

    public int[] subSort(int[] array) {
        
        //隐含条件：示例给出的数组大体上可以看出是从小到大排列

        //0. 边界判断
        if(array==null) return array;
        if(array.length==0||array.length==1) return new int[]{-1,-1};

        //1.从左到右扫描 寻找逆序对(正序：从小到大)
        int max = array[0];//先假设第一个就是左侧最大值
        int r = -1;//最右逆序对
        for(int i = 1;i<array.length;i++) {
            int val = array[i];
            if(val < max) {//说明是逆序对 记录下来
                r = i;
            }else {//>=更新最大值
                max = val;
            }
        }

        //2.扫描一遍没有发现逆序对 说明整个数组本来就有序
        if(r==-1) return new int[]{-1,-1};

        //3.从右往左扫描 寻找逆序对(正序：从大到小)
        int min = array[array.length-1];//右侧最小值
        int l = -1;//最左逆序对
        for(int i = array.length-1;i>=0;i--) {
            int val  = array[i];
            if(val <= min) { //遇到比min更小就更新min
                min = val;
            }else {// > 说明是逆序对 记录下来
              l = i;
            }
        }

        //4.返回结果
        return new int[]{l,r};

    }
}