欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[LeetCode]581. Shortest Unsorted Continuous Subarray

程序员文章站 2022-03-07 18:28:01
...

[LeetCode]581. Shortest Unsorted Continuous Subarray

题目描述

[LeetCode]581. Shortest Unsorted Continuous Subarray

思路

找出对应的最大最小值,看是否在对应的位置,如果在就向中间缩小,如果都不在,计算长度
暴力解法,平方复杂度
缩小是n,找最大最小是n
优化1,先排序,比较对应位置,时间复杂度 nlogn
继续优化,找局部最大最小可以用动归思路实现,找到好保存状态数组
可以将找最大最小优化到常数时间,最后时间复杂度为n

代码

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

using namespace std;

class Solution {
public:
    /* 
    //暴力解法
    int findUnsortedSubarray(vector<int>& nums) {
        int start = 0, end = nums.size() - 1;
        while (start < end) {
            vector<int> minMax = getMinMaxIndex(nums, start, end);
            int min = minMax[0], max = minMax[1];
            if (min != start && max != end)
                break;
            if (min == start)
                start++;
            if (max == end)
                end--;
        }
        return start >= end ? 0 : end - start + 1;
    }

    vector<int> getMinMaxIndex(vector<int> nums, int start, int end) {
        int min = start, max = start;
        for (int i = start; i <= end; ++i) {
            min = nums[i] < nums[min] ? i : min;
            max = nums[i] >= nums[max] ? i : max;
        }
        vector<int> res = { min, max };
        return res;
    }
    */

    /* 
    //排序后的解法
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> sortArr = nums;
        sort(sortArr.begin(), sortArr.end());
        int start, end;
        for (start = 0; start < nums.size(); ++start) {
            if (nums[start] != sortArr[start])
                break;
        }
        for (end = nums.size() - 1; end >= 0; --end) {
            if (nums[end] != sortArr[end])
                break;
        }
        return start >= end ? 0 : end - start + 1;
    }
    */

    //最后优化
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> r2lMin = nums, l2rMax = nums;
        r2lMin[nums.size() - 1] = nums[nums.size() - 1], l2rMax[0] = nums[0];
        for (int i = nums.size() - 2; i >= 0; --i) {
            r2lMin[i] = min(nums[i], r2lMin[i + 1]);
        }
        for (int i = 1; i < nums.size(); ++i) {
            l2rMax[i] = max(nums[i], l2rMax[i - 1]);
        }

        int start, end;
        for (start = 0; start < nums.size(); ++start) {
            if (nums[start] != r2lMin[start])
                break;
        }
        for (end = nums.size() - 1; end >= 0; --end) {
            if (nums[end] != l2rMax[end])
                break;
        }
        return start >= end ? 0 : end - start + 1;
    }

};

int main() {
    vector<int> nums = { 1,3,2,3,3 };
    Solution s;
    cout << s.findUnsortedSubarray(nums) << endl;

    system("pause");
    return 0;
}
相关标签: leetcode