佛山做网站哪家好,360免费wifi手机版,网站seo技巧,免费流程图制作网站上一篇: 算法随笔_11: 字符串的排列-CSDN博客
题目描述如下:
给你一个整数数组 nums #xff0c;你需要找出一个 连续子数组 #xff0c;如果对这个子数组进行升序排序#xff0c;那么整个数组都会变为升序排序。请你找出符合题意的最短子数组#xff0c;并输出它的长度。…上一篇: 算法随笔_11: 字符串的排列-CSDN博客
题目描述如下:
给你一个整数数组 nums 你需要找出一个 连续子数组 如果对这个子数组进行升序排序那么整个数组都会变为升序排序。请你找出符合题意的最短子数组并输出它的长度。
示例 1
输入nums [2,6,4,8,10,9,15]
输出5
解释你只需要对 [6, 4, 8, 10, 9] 进行升序排序那么整个表都会变为升序排序。 我们一起来分析一下这道题。
需要找出的这个子数组可以是任意的位置。不失一般性的我们可以假设这个子数组的起始点在原来数组的中间某处。我们假设这个子数组为nums_mid那么此时它分割出来左右两个子数组分别为nums_leftnums_right。按照题意如果对子数组nums_mid进行升序排序整个数组都会变为升序排序那么原数组应该有以下的特征:
仅对子数组nums_mid进行升序排序就相当于对全数组进行了排序。反过来说对全数组进行排序其实只是把nums_mid进行了排序。在排序的前后nums_leftnums_right两个子数组的序列是不变的。
基于此特征我们可以写出如下算法:
我们对原数组进行升序排序。排序之后我们把排序之后的数组与原数组从左到右逐个字符的进行比较。当发现第一个出现不同的字符时我们就找到了nums_left。同理从右至左逐个字符的进行比较我们就找到nums_right。那么中间的这一块儿就是nums_mid。其长度即可算出。
此算法的时间复杂度为O(nlogn) 。 让我们再考虑一下有没有更优的算法
让我们重新审视一下原题的描述。nums_mid不论是否排序它里面的任何一个元素都比nums_left中的任何一个元素大。nums_right在排序前后本身就不改变序列因此它的任何一个元素也比nums_left的任何一个元素大。因此nums_left有如下特征:
1. 它是一个升序排列。
2. 它的最大值一定比后面所有数的最小值还要小。
基于此特征我们可以给出如下的算法:
1. 我们设置两个变量nums_left_max(表示nums_left的最大值的下标)和left_min(表示nums_left后面所有数的最小值)。
2. 我们从右向左遍历原数组记录当前已经遍历过的元素的最小值left_min。并且每个当前访问的元素e和left_min比较会有下面两种情况: a. 如果e小于left_min并且nums_left_max为-1我们记录当前下标为nums_left_max。 b. 如果e大于left_min那么nums_left_max肯定不为当前的下标。我们把nums_left_max重置为1。
遍历完成后我们就找到了nums_left_max。
同理我们可以求出nums_right_min(表示nums_right的最小值的下标)。
最终两数相减即为题目答案。由于此算法只执行了一次遍历因此时间复杂度为O(N) 。
算法具体实现时注意一下边界条件。实际代码如下:
class Solution(object):def findUnsortedSubarray(self, nums):nlen(nums)nums_left_max-1nums_right_minnleft_minfloat(inf)right_maxfloat(-inf)for i in range(n):if right_maxnums[i]:right_maxnums[i]if nums_right_minn:nums_right_minielse:nums_right_minnif left_minnums[n-i-1]:left_minnums[n-i-1]if nums_left_max-1:nums_left_maxn-i-1else:nums_left_max-1retnums_right_min-nums_left_max-1ret0 if ret0 else retreturn ret
