[리트코드] 581. Shortest Unsorted Continuous Subarray

581. Shortest Unsorted Continuous Subarray

문제

Given an integer array nums, 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.

Return the shortest such subarray and output its length.

어떤 부분 배열만 정렬하면 전체가 정렬되는 부분 배열 찾기

제한사항

• 1 <= nums.length <= 104
• -105 <= nums[i] <= 105

풀이

제일 간단히 풀 수 있는 방법

배열을 복사해서 정렬한 후 앞에서 처음으로 다른 인덱스와

뒤에서 처음으로 다른 인덱스 사이의 배열의 길이를 리턴하면 된다.

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        nums2 = sorted(nums)
        start, end = 0, 0
        
        if nums2 == nums:
            return 0
        
        for i in range(len(nums)):
            if nums[i] != nums2[i]:
                start = i
                break
        
        for i in range(len(nums) - 1, 0, -1):
            if nums[i] != nums2[i]:
                end = i
                break
        
        return len(nums[start:end + 1])

다른 방식

처음으로 오름차순이 아닌 곳 찾기 - start

뒤에서부터 처음으로 내림차순이 아닌 곳 찾기 - end

만약 start 값이 end보다 클 경우 이미 모든 값이 정렬되어 있다는 뜻이므로 0을 리턴한다.

[start : end]의 최대값, 최소값 구하기

최소값보다 작은 값을 찾을 때까지 왼쪽으로 이동

최대값보다 큰 값을 찾을 때까지 오른쪽 이동

end - start + 1 한 값이 답이 된다.

upper bound와 lower bound를 적용한다고 생각하면 된다.

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        start, end = 0, len(nums) - 1
        
        if len(nums) < 2:
            return 0
        
        while start < len(nums) - 1 and nums[start] <= nums[start + 1]:
            start += 1
        
        while end > 0 and nums[end] >= nums[end - 1]:
            end -= 1
        
        if start > end:
            return 0
        
        tmp = nums[start:end + 1]
        tmpMin = min(tmp)
        tmpMax = max(tmp)
        
        while start > 0 and tmpMin < nums[start - 1]:
            start -= 1
        
        while end < len(nums) - 1 and tmpMax > nums[end + 1]:
            end += 1
            
        return end - start + 1