部分排序

面试题 16.16. 部分排序

难度中等61

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

解题思路

• 从左往右找逆序的最大值，最大值的位置就是无序的右边界

• 从右往左找逆序的最小值，最小值的位置就是无需的左边界

菜鸡的写法

class Solution {
    public int[] subSort(int[] array) {
        if (array == null || array.length == 0) return new int[]{-1, -1};

        int len = array.length;

        int max = Integer.MIN_VALUE;
        boolean flag = false;
        // 从后往前找到逆序的最大值
        for (int i = len - 1; i > 0; i--) {
            if (array[i] < array[i - 1]) flag = true;
            if (flag) max = Math.max(max, array[i]);            
            //找逆序后的左边的最大值，最大值的位置即为无序的右边界
        }
        flag = false;
        int min = Integer.MAX_VALUE;
        // 从前往后找到逆序的最小值
        for (int i = 0; i < len - 1; i++) {
            if (array[i] > array[i + 1]) flag = true;
            if (flag) min = Math.min(min, array[i]);            
            //找逆序后的最小值，最小值的真正位置即为无序的左边界
        }

        int left = -1, right = -1;
        for (int i = 0; i < len; i++) {
            if (array[i] > min) {
                left = i;
                break;
            }
        }
        for (int i = len - 1; i >= 0; i--) {
            if (array[i] < max) {
                right = i;
                break;
            }
        }

        return new int[]{left, right};
    }
}

优雅的写法

class Solution {
    public int[] subSort(int[] array) {
        if(array == null || array.length == 0) return new int[]{-1, -1};
        int last = -1, first = -1;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int len = array.length;

        for(int i = 0; i < len; i++){
            if(array[i] < max){
                //如果当前数字小于目前遍历的最大值，说明他是逆序的，记录最后一个逆序的位置
                last = i;
            }else{
                max = Math.max(max, array[i]);
            }

            if(array[len - 1 - i] > min){                   
                //如果一个数字小于当前遍历到的最小值，说明他是逆序的，记录最前面的一个逆序的位置
                first = len - 1 - i;
            }else{
                min = Math.min(min, array[len - 1 - i]);
            }
        }
        return new int[] {first, last};
    }
}

作者：chen-wei-zhe
链接：https://leetcode-cn.com/problems/sub-sort-lcci/solution/yi-bian-bian-li-shuang-zhi-zhen-by-chen-wei-zhe/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

高效的写法

class Solution {
    public int[] subSort(int[] array) {
        if (array.length == 0) return new int[]{-1,-1};
        int start = 0;
        int max = array[0];
        int r = -1;
        for (int i = 1; i < array.length; i++) {
            if (array[i] >= max) {
                max = array[i];
            }else {
                r = i;
            }
        }

        int l = -1;
        int min = array[array.length - 1];
        for (int i =  array.length-1; i >= 0; i--) {
            if (array[i] <= min) {
                min = array[i];
            }else {
                l = i;
            }
        }
        return new int[]{l, r};
    }
}

作者：user0230C
链接：https://leetcode-cn.com/problems/sub-sort-lcci/solution/zui-hao-li-jie-de-fang-shi-ji-bai-bai-fen-zhi-99-b/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信