hiho一下第208周《Smallest Sub Array》题目分析

2
0

《Smallest Sub Array》题目分析

本题的大意是对一个包含N个整数的数组,找到一个最短的连续子数组,使得只要把子数组的数从小到大排序之后,整个数组就是排好序的了。

这道题比较简单。一个很暴力的算法是直接将原数组A排序,得到排好序的数组B

然后从左到右比较依次A[i]B[i],找到第一个不相同的位置p;再从右到左依次比较找到第一个不相同的位置q

那么A[p] ... A[q]这一段就是所求。

这个算法由于要先排序,所以复杂度是O(NlogN)的,可以通过所有的数据。

实际上沿着这个思路可以免去排序,将算法优化到O(N)。留给同学们自己思考~

3 answer(s)

0

n/a

0

n复杂度实现,欢迎来博客下方和我交流想法 https://blog.csdn.net/qq_31964727/article/details/80803672

  • 我的想法和你有点不同,就是找到边界后,边界值与数组的最大最小值的位置进行比较即可,如果你找到的边界值,比整个数组的最小值的位置都要小的时候,说明最左边的边界是0

  • 添加评论
  • reply
0

前后各维护一个单调栈,前面的不减,后面的不增 答案即为 n-前单调栈与a最长前缀-后单调栈与a最长后缀 特判a已经排好序

write answer 切换为英文 切换为中文


转发分享