정수 배열이 있다고 가정하고 하나의 연속 하위 배열을 찾아야만 해당 하위 배열을 오름차순으로 정렬하면 전체 배열도 정렬됩니다. 우리는 그러한 가장 짧은 부분배열을 찾아 그 길이를 출력해야 합니다. 따라서 배열이 [2,6,4,8,10,9,15]이면 출력은 5가 됩니다. 배열은 [6,4,8,10,9]
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
res :=숫자를 배열로 정렬
-
답변 :=0
-
r을 연결 목록으로 설정
-
범위 0에서 res의 길이까지의 i에 대해
-
nums[i]가 res[i]와 같지 않으면 i를 r
에 삽입합니다.
-
-
r의 길이가 0이면 0을 반환하고 r의 길이가 1이면 1을 반환
-
r의 마지막 요소를 반환 - r + 1의 첫 번째 요소
예제(파이썬)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
class Solution(object): def findUnsortedSubarray(self, nums): res = sorted(nums) ans = 0 r = [] for i in range(len(res)): if nums[i] != res[i]: r.append(i) if not len(r): return 0 if len(r) == 1: return 1 return r[-1]-r[0]+1 ob1 = Solution() print(ob1.findUnsortedSubarray([2,6,4,8,10,9,15]))
입력
[2,6,4,8,10,9,15]
출력
5