Python에서 하나의 스왑으로 이전 순열

양의 정수 배열 A가 있다고 가정하고(반드시 고유하지는 않음), A보다 작은 사전순으로 가장 큰 순열을 찾아야 하며, 이는 한 번의 교환으로 만들 수 있습니다(교환은 두 숫자 A[i]의 위치를 ​​교환하고 에이[제]). 가능하지 않은 경우 동일한 배열을 반환합니다. 따라서 배열이 [3,2,1]과 같으면 출력은 2와 1을 교환하여 [3,1,2]가 됩니다.

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

• n :=A의 크기
• n – 2에서 -1까지 범위의 왼쪽
  • left =-1이면 A를 반환하고, 그렇지 않으면 A[left]> A[left + 1]이면 중단
• 요소:=0, 색인:=0
• 왼쪽 범위의 오른쪽 + 1 ~ n
  • A[right] 요소이면
    • 요소 =A[오른쪽]
    • 색인 :=오른쪽
• A[왼쪽] 및 A[색인] 교체
• 리턴 A

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

예시

class Solution(object):
   def prevPermOpt1(self, A):
      n = len(A)
      for left in range(n-2,-2,-1):
         if left == -1:
            return A
         elif A[left]>A[left+1]:
            break
      element = 0
      index = 0
      for right in range(left+1,n):
         if A[right]<A[left] and A[right]>element:
            element = A[right]
            index = right
      temp = A[left]
      A[left] = A[index]
      A[index] = temp
      return A
ob = Solution()
print(ob.prevPermOpt1([4,2,3,1,3]))

입력

[4,2,3,1,3]

출력

[4, 2, 1, 3, 3]