Python에서 선형 시간으로 크기가 3인 정렬된 하위 시퀀스 찾기

N개의 숫자가 있는 배열이 있다고 가정하고 선형(O(n)) 시간에 b[i]

따라서 입력이 [13, 12, 11, 6, 7, 3, 31]과 같으면 출력은 [6,7,31]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=A의 크기
• 최대:=n-1, 최소:=0
• smaller :=크기가 1000이고 0으로 채워지는 배열
• 작게[0] :=-1
• 1~n 범위의 i에 대해
  • A[i] <=A[최소값]이면
    • 최소 :=나
    • 작게[i] :=-1
  • 그렇지 않으면
    • 작은[i] :=최소
• Greater :=크기가 1000이고 0으로 채워지는 배열
• 크다[n-1] :=-1
• n-2 ~ -1 범위의 i에 대해 1 감소, do
  • A[i]>=A[최대]이면
    • 최대:=나
    • 크게[i] :=-1
  • 그렇지 않으면
    • 크게[i] :=최대값
• 0에서 n 사이의 i에 대해
  • 작은[i]가 -1과 같지 않고 더 큰[i]가 -1과 같지 않으면
    • A[작은[i]], A[i], A[큰[i]] 반환
• "아무것도" 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def find_inc_seq(A):
   n = len(A)
   maximum = n-1
   minimum = 0
   smaller = [0]*10000
   smaller[0] = -1
   for i in range(1, n):
      if (A[i] <= A[minimum]):
         minimum = i
         smaller[i] = -1
      else:
         smaller[i] = minimum
   greater = [0]*10000
   greater[n-1] = -1
   for i in range(n-2, -1, -1):
      if (A[i] >= A[maximum]):
         maximum = i
         greater[i] = -1
      else:
         greater[i] = maximum
   for i in range(0, n):
      if smaller[i] != -1 and greater[i] != -1:
         return A[smaller[i]], A[i], A[greater[i]]
   return "Nothing"
arr = [13, 12, 11, 6, 7, 3, 31]
print(find_inc_seq(arr) )

입력

[13, 12, 11, 6, 7, 3, 31]

출력

(6, 7, 31)