다음 순열

정수 배열의 순열은 구성원을 시퀀스 또는 선형 순서로 배열하는 것입니다.

예를 들어, arr = [1,2,3] 의 경우 다음은 arr 의 순열로 간주됩니다: [1,2,3] , [1,3,2] , [3,1,2] , [2,3,1] .

정수 배열의 다음 순열은 정수의 사전순으로 다음 순열입니다. 보다 공식적으로, 배열의 모든 순열이 사전식 순서에 따라 하나의 컨테이너에 정렬된 경우 해당 배열의 다음 순열은 정렬된 컨테이너에서 뒤따르는 순열입니다. 이러한 정렬이 불가능하면 배열을 가능한 가장 낮은 순서로 다시 정렬해야 합니다(즉, 오름차순으로 정렬).

예를 들어 arr = [1,2,3]의 다음 순열은 [1,3,2]입니다.

마찬가지로 arr = [2,3,1]의 다음 순열은 [3,1,2]입니다.

arr = [3,2,1]의 다음 순열은 [1,2,3]에 사전식으로 더 큰 재배열이 없기 때문에 [3,2,1]입니다.

정수 배열 nums 이 주어지면 nums 의 다음 순열을 찾습니다.

교체는 in place이어야 하며 일정한 추가 메모리만 사용해야 합니다.

예 1:

입력: 숫자 = [1,2,3]
출력: [1,3,2]

예 2:

입력: 숫자 = [3,2,1]
출력: [1,2,3]

예 3:

입력: 숫자 = [1,1,5]
출력: [1,5,1]

제약:

1 <= nums.length <= 100

0 <= nums[i] <= 100

해결책:

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        i = n - 1
        while i > 0:
            if nums[i - 1] < nums[i]:
                break
            i -= 1
        if i == 0:
            nums.reverse()
            return
        mdiff = float('inf')
        closest = None
        for j in range(i, n):
            if nums[j] > nums[i - 1] and nums[j] - nums[i - 1] <= mdiff:
                mdiff = nums[j] - nums[i - 1]
                closest = j
        if closest:
            nums[i - 1], nums[closest] = nums[closest], nums[i - 1]
        for j in range(i, (i + n) // 2):
            nums[j], nums[n - j + i - 1] = nums[n - j + i - 1], nums[j]