当前位置：首页 > news >正文

[力扣c++实现] 581. 最短无序连续子数组

news 来源：原创 2024/11/20 8:29:29

581. 最短无序连续子数组

给你一个整数数组 nums ，你需要找出一个连续子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的最短子数组，并输出它的长度。

示例 1：

输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
示例 2：

输入：nums = [1,2,3,4]
输出：0
示例 3：

输入：nums = [1]
输出：0

提示：

1 <= nums.length <= 104
-105 <= nums[i] <= 105

进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shortest-unsorted-continuous-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1.c++

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

class Solution {
public:
    int findUnsortedSubarray(std::vector<int>& nums) {
        std::vector<std::pair<int,int>> value2Seq;
        int size = (int)nums.size();
        for (int i = 0 ; i < size; ++i)
        {
            value2Seq.push_back({nums[i],i});
        }
        
        std::vector<std::pair<int,int>> v2SwithSort = value2Seq;
        std::stable_sort(v2SwithSort.begin(),v2SwithSort.end(),[&](const auto p1,const auto p2){
            return p1.first < p2.first;
        });

        //找到不同的交集
        int i = 0;
        std::vector<std::pair<int,int>> subSeqs;
        while (i < size)
        {
            int start = -1;
            int end = -1;
            while (i < size && v2SwithSort[i] == value2Seq[i])
            {
                ++i;
            }

            start = i;

            while (i < size && v2SwithSort[i] != value2Seq[i])
            {
                ++i;
            }

            if (start == i)//so important,why?
                break;
            end = i;
            subSeqs.push_back({start,end});
        }
        
        if (subSeqs.size() < 1)
            return 0;
        int start = subSeqs[0].first;
        int end = subSeqs[(int)subSeqs.size() - 1].second;
        return end - start;
    }
};

int main()
{
    Solution slu;
    std::vector<int> nums = {2,6,4,8,10,9,15};
    std::cout << slu.findUnsortedSubarray(nums) << std::endl;
    return 0;
}