581. 最短无序连续子数组

581. 最短无序连续子数组

 

 

 

 思路:

1、从左往右遍历,每一趟找出此前的最大值max,若nums[i]<max,则num[i]是需要参与重排的;
2、遍历到最右端,记录下最右边一个需要重排元素,其下标为high;
3、从右往左遍历,每一趟找出此前的最小值min,若nums[i]>min,则num[i]是需要参与重排的;
4、遍历到最左端,记录下最左边一个需要重排元素,其下标为low;
5、在nums中下标从low到high的元素即是需要重排的,返回值为:high-low+1。
注:若nums本就升序排列,则无需重排,返回值是0。

python中,倒序遍历list:从最后一个元素循环到第一个元素:
 for i in range(len(nums) - 1, -1, -1): 

本题代码实现:
 1 class Solution(object):
 2     def findUnsortedSubarray(self, nums):
 3         """
 4         :type nums: List[int]
 5         :rtype: int
 6         """
 7         # 从左往右遍历,找high
 8         # big用来记录每一趟的最大值
 9         big = nums[0]
10         high = 0
11         for i in range(1, len(nums)):
12             # 记录需要参与重排的元素的下标
13             if nums[i] < big:
14                 high = i
15             # 更换遍历中的最大值
16             elif nums[i] > big:
17                 big = nums[i]
18         # 从右往左遍历,找low
19         # small用来记录每一趟遍历的最小值
20         small = nums[-1]
21         low = len(nums) - 1
22         for j in range(len(nums) - 1, -1, -1):
23             # 记录需要参与重排的元素的下标
24             if nums[j] > small:
25                 low = j
26             # 更变遍历中的最小值
27             elif nums[j] < small:
28                 small = nums[j]
29         # 若nums本就升序,无需重排
30         if low - high + 1 == len(nums):
31             return 0
32         # 否则返回high - low + 1
33         else:
34             return high - low + 1
35 
36 
37 if __name__ == '__main__':
38     solution = Solution()
39     # print(solution.findUnsortedSubarray([1, 2, 3, 4]))
40     print(solution.findUnsortedSubarray([2, 6, 4, 8, 10, 9, 15]))
若nums本就有序时也可在代码前先做处理:
1 #升序排
2 s = sorted(nums)
3 #排序前后一致
4 if nums == s:
5     return 0

 
上一篇:[LeetCode] 581. Shortest Unsorted Continuous Subarray


下一篇:力扣编程题分析(581):最短无序连续子数组