首页 > 其他 > 详细

2021-8-3 Shortest Unsorted Continuous Subarray

时间:2021-08-04 11:32:28      阅读:16      评论:0      收藏:0      [点我收藏+]

难度 中等

题目 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

原文:https://www.cnblogs.com/lovetianyi/p/15096892.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!