面试题 16.16

Given an array of integers, write a method to find indices m and n such that if you sorted elements m through n, the entire array would be sorted. Minimize n - m (that is, find the smallest such sequence).

Return [m,n]. If there are no such m and n (e.g. the array is already sorted), return [-1, -1].

Example:

Input: [1,2,4,7,10,11,7,12,6,7,16,18,19] Output: [3,9] Note:

0 <= len(array) <= 1000000

Solutions

• Similar to problem 581, check for detailed explanation.

• two scanning

class Solution {
public:
    vector<int> subSort(vector<int>& array) {
        if (!array.size()) return {-1, -1};
        int n = array.size();

        int li = -1, minv = INT_MAX; 
        for (int i = n - 1; i >= 0; i--) {
            if (array[i] <= minv)
                minv = array[i];
            else
                li = i;
        }

        int ri = -1, maxv = INT_MIN;
        for (int i = 0; i < n; i++) {
            if (array[i] >= maxv)
                maxv = array[i];
            else
                ri = i;
        }

        return {li, ri};
    }
};