《Smallest Sub Array》题目分析
本题的大意是对一个包含N
个整数的数组,找到一个最短的连续子数组,使得只要把子数组的数从小到大排序之后,整个数组就是排好序的了。
这道题比较简单。一个很暴力的算法是直接将原数组A
排序,得到排好序的数组B
。
然后从左到右比较依次A[i]
和B[i]
,找到第一个不相同的位置p
;再从右到左依次比较找到第一个不相同的位置q
。
那么A[p] ... A[q]
这一段就是所求。
这个算法由于要先排序,所以复杂度是O(NlogN)
的,可以通过所有的数据。
实际上沿着这个思路可以免去排序,将算法优化到O(N)
。留给同学们自己思考~
我的想法和你有点不同,就是找到边界后,边界值与数组的最大最小值的位置进行比较即可,如果你找到的边界值,比整个数组的最小值的位置都要小的时候,说明最左边的边界是0