题目分析

我个人很喜欢这样的题目，题目难度适中，题意清晰，简洁。一道题上来就是一大段文字，比较晦涩的那种，我比较头痛。废话少说，小伙伴们看题。

排序

这个题目的意思是，有一个排好序的数组，其中有一个区间内数据打乱了，我们要找到这个最小的区间。

我的直观想法是，既然最后整个数组是有序的，那么我们可以将排好序的结果打印出来，然后进行对比，看一看从哪里开始不同的，到哪里相同不就是找到了这个区间吗？

算法的**时间复杂度为$O(nlog(n))$，空间复杂度为$O(n)$**。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class Solution {
public:
    vector<int> subSort(vector<int>& array) {
        vector<int> sortArray(array);
        sort(sortArray.begin(), sortArray.end());
        int left = 0, right = array.size() - 1;
        while (left < array.size() && array[left] == sortArray[left]) { left++; }
        while (right >= 0 && array[right] == sortArray[right]) { right--; }
        return left < right ? vector<int>{ left, right } : vector<int>{ -1, -1 };
    }
};

数学

这个题目还有时间复杂度更短的做法，这用到了一些数学知识。如果第k个数，小于前k - 1个数的最大值，那么k一定是区间内的，因此我们可以找到最后一个k，当m > k时，都大于等于前m - 1个数的最大值。那么这个k就是这个区间的右端点。

同理，如果第k个数，大于后面所有数字的最小值，那么k也是这个区间内的，我们找到第一个k，当m < k时，都小于等于后面所有数字的最小值，那么这个k就是这个区间的左端点。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(1)$**。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    vector<int> subSort(vector<int>& array) {
        int maxi = INT32_MIN, mini = INT32_MAX, left = -1, right = -1;
        for (int i = 0; i < array.size(); i++) {
            if (array[i] < maxi) { right = i; }
            else { maxi = array[i]; }
            if (array[array.size() - 1 - i] > mini) { left = array.size() - 1 - i; }
            else { mini = array[array.size() - 1 - i]; }
        }
        return { left, right };
    }
};

刷题总结

现在是寒假时间，寒假结束后，暑期实习，春招就要来到了，很多公司的提前批也是方法春天进行的，因此小伙伴们在放假长膘的期间内别忘了加强自己的coding能力。