题解 | #最短无序连续子数组#
最短无序连续子数组
http://www.nowcoder.com/practice/d17f4abd1d114617b51e951027be312e
提供个思路，不知道该叫啥算法。（贪心？）
找出从０开始的最长有效有序序列（以n-1为终点的同理）：
第一，比较相邻的数字，第一次出现nums[i]>nums[i+1]时,标记flag=1，并记录下指标i
第二，找出nums[i:]之中的最小值min
第三，如果flag=0,即没有遇到逆序，直接返回零；如果flag=1,则需要回溯nums[:i],找到第一个小于min的值的指标ind1，这个指标ind1就是从０开始的最长有效有序序列的终点了，同理找出ind2(以n-1为终点的最长有效有序序列），然后返回 ind2-ind1-1
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可#
#
# @param nums int整型一维数组
# @return int整型
#
class Solution: def findUnsortedSubarray(self , nums: List[int]) -> int: # write code here ind1,flag1,ind2,flag2,len0=0,0,0,0,len(nums) for i in range(len0): if not flag1 and i<len0-1 and nums[i]>nums[i+1]: ind1,flag1,min1=i,1,nums[i+1] elif flag1: min1=min(min1,nums[i]) if not flag2 and i<len0-1 and nums[len0-1-i]<nums[len0-2-i]: ind2,flag2,max2=len0-1-i,1,nums[len0-2-i] elif flag2: max2=max(max2,nums[len0-1-i]) if not flag1: return 0 while ind1>=0: if nums[ind1]<=min1: break else: ind1+=-1 while ind2<=len0-1: if nums[ind2]>=max2: break else: ind2+=1 return ind2-ind1-1
哔哩哔哩公司福利 739人发布
查看26道真题和解析
