2021-8-3 Shortest Unsorted Continuous Subarray

本文主要是介绍2021-8-3 Shortest Unsorted Continuous Subarray，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

难度 中等

题目 Leetcode:

Shortest Unsorted Continuous Subarray

Given an integer array nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.

Return the shortest such subarray and output its length.

题目解析

这样一题的思路其实是很简单的，我这里用multiset直接排序一遍，从头找不同和从尾找不同，两个一相减就是需要重新排列的元素的个数。

这题的毫无疑问有更多优化的思路，或者说这题有更好的解决方法，这里不多赘述，后续会更新一些新学到的方法。

解析完毕，以下是参考代码

 1 class Solution {
 2 public:
 3     int findUnsortedSubarray(vector<int>& nums) {
 4         int len=nums.size();
 5         multiset<int>temp;
 6         for(int i=0;i<len;i++)
 7         {
 8             temp.insert(nums[i]);
 9         }
10         int st=0,en=0;
11         auto x=temp.begin();
12         for(int i=0;i<len;i++)
13         {
14             if(*x!=nums[i])
15             {
16                 st=i;
17                 break;
18             }
19             x++;
20         }
21         x=temp.end();
22         x--;
23         for(int i=len-1;i>=0;i--)
24         {
25             if(*x!=nums[i])
26             {
27                 en=i;
28                 break;
29             }
30             x--;
31         }
32         return (en==0&&st==0)?0:en-st+1;
33     }
34 };

这篇关于2021-8-3 Shortest Unsorted Continuous Subarray的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！