欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[easy][Array]581. Shortest Unsorted Continuous Subarray

程序员文章站 2024-02-24 14:57:04
...

原题是:

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Example 1:
Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
Note:
Then length of the input array is in range [1, 10,000].
The input array may contain duplicates, so ascending order here means <=.

思路:

这个题需要思路宏观一点。
用两个指针分别从数组的开头和末尾开始,与该数组排序好的版本逐个元素进行比较。
记录元素不同的第一个i,第一个j。
i,j 的距离就是所求的需要调整顺序最小子数组。
注意,i,j可能彼此“穿越”,所以只有当结果是大于0的时候才是所需结果。如果小于等于0,说明数组完全不需要调整任何子数列的升序,返回0.

代码是:

class Solution:
    def findUnsortedSubarray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        sort = sorted(nums)
        i = 0
        j = -1
        while i < len(nums):
            if nums[i] != sort[i]:
                break
            else:
                i += 1
                
        while j >= -len(nums):
            if nums[j] != sort[j]:
                break
            else:
                j -=1
        
        ans = len(nums) - i + j +1
        return ans if ans >0 else 0