一、题目
给定一个整数数组,你需要寻找一个连续的子数组,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。
你找到的子数组应是最短的,请输出它的长度。
示例 1:
输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序,那么整个表都会变为升序排序。
说明 :
输入的数组长度范围在 [1, 10,000]。
输入的数组可能包含重复元素 ,所以升序的意思是<=。
二、解题思路
1、排序对比:将数组按升序排序,然后与原数组对照,从哪里开始变化到哪里结束变化的数组就是答案。
注意事项: 列表自带排序函数some_list.sort(),但不能用在这道题里,因为这个排序方法会改变原列表,而我们需要原列表来做对比,所以不能用。可以用sorted(some_list)方法,不会改变原列表,而是会返回一个新的已经排序好的list。
2、 别人的代码:效率更高,时间复杂度O(n),空间复杂度O(1)。但很难想到,放到下面供学习参考。
注意事项:从提交结果来看,两种方法差别不大。
三、代码
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
new_nums=sorted(nums)
change_num=[]
if new_nums==nums:return 0
for i in range(len(nums)):
if nums[i] != new_nums[i]:
change_num.append(i)
change_num=nums[change_num[0]:change_num[-1]+1]
return len(change_num)
2. 别人的代码,更优解
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
n=len(nums)
max_num=nums[0]
right=0
for i in range(n):
if(nums[i]>=max_num):
max_num=nums[i]
else:
right=i
left=n
min_num=nums[-1]
for i in range(n-1,-1,-1):
if(nums[i]<=min_num):
min_num=nums[i]
else:
left=i
return right-left+1 if(right-left+1 >0) else 0
作者:wu_yan_zu
链接:https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/liang-ci-bian-li-pai-xu-bi-dui-python3-by-zhu_shi_/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
本文地址:https://blog.csdn.net/Lucy_R/article/details/107638765
如对本文有疑问, 点击进行留言回复!!
python中逻辑与或(and、or)和按位与或异或(&、|、^)区别
基于Python编写一个计算器程序,实现简单的加减乘除和取余二元运算
网友评论