Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python에서 정렬되지 않은 가장 짧은 연속 하위 배열


정수 배열이 있다고 가정하고 하나의 연속 하위 배열을 찾아야만 해당 하위 배열을 오름차순으로 정렬하면 전체 배열도 정렬됩니다. 우리는 그러한 가장 짧은 부분배열을 찾아 그 길이를 출력해야 합니다. 따라서 배열이 [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