AI编程社区

Given an array, find the minimum length unsorted subarray. After soring this unsorted subarray,

the whole array is sorted.

 

Example, if the input array is [10, 12, 20, 30, 25, 40, 32, 31, 45, 50, 60], your program should be 

able to find that the minimum length unsorted subarray lies between the indices 3 and 7.

 

Solution 1. O(n * logn) runtime, O(n) space

1. make a copy of the given array.

2. sort the copy.

3. find the first and last indices where the given array and its sorted copy don't match .

 

Solution 2. O(n) runtime, O(1) space

The core idea of this solution is to first find the start index i of the unsorted subarray where arr[i] < arr[i- 1], 

and use arr[i - 1] as the current max value. 

Then keep scaning the rest of the array, as long as arr[i] < arr[i - 1] or arr[i] is smaller than the max value, 

we know that arr[i] is not in its sorted place. Update end index to i.

If arr[i] is bigger than max, update the current max to arr[i].

 

public int[] getMinLenUnsortedSubarray(int[] arr) {
    int[] r = {-1, -1};
    if(arr == null || arr.length <= 1) {
        return r;
    }
    int i = 1;
    for(; i < arr.length; i++){
        if(arr[i] < arr[i - 1]) {
            break;
        }
    }
    if(i == arr.length - 1){
        return r;            
    }
    r[0] = i - 1;
    r[1] = i;
    int max = arr[i - 1];
    for(i++; i < arr.length; i++){
        if(arr[i] < arr[i - 1] || arr[i] < max){
            r[1] = i;
        }
        else if(arr[i] >= max){
            max = arr[i];
        }
    }
    return r;
}