Leetcode: 다음 순열

이것은 일련의 Leetcode 및 기타 선별된 솔루션 설명(색인)의 일부입니다.
이 솔루션이 마음에 드셨거나 유용하셨다면 이 게시물에 좋아요를 눌러주세요.

Leetcode Problem #31 (Medium): Next Permutation

31. 다음 순열

숫자를 사전순으로 다음으로 큰 숫자 순열로 재배열하는 다음 순열을 구현합니다.

이러한 배열이 가능하지 않은 경우 가능한 가장 낮은 순서로 재배열해야 합니다(즉, 오름차순으로 정렬).

교체는 제자리에 있어야 하며 일정한 추가 메모리만 사용해야 합니다.

예 1:

Input: nums = [1,2,3]
Output: [1,3,2]

예 2:

Input: nums = [3,2,1]
Output: [1,2,3]

예 3:

Input: nums = [1,1,5]
Output: [1,5,1]

예 4:

Input: nums = [1]
Output: [1]

제약 조건:

1 <= nums.length <= 100
0 <= nums[i] <= 100

해결책

아이디어는 약간 까다롭습니다. 우선 답은 숫자가 아니라 입력 배열에 표시된 숫자의 재배열입니다. 이것은 인덱스 10으로 숫자를 계산할 필요가 없다는 힌트를 줄 수 있습니다.

또는

그 솔루션을 무차별 대입으로 생각할 수 있습니다.

입력의 모든 순열을 생성합니다.

해당 입력 변형에서 숫자를 생성합니다.

다음으로 큰 찾기
이 시점에서 배열을 HashMap 인덱스로 저장하고 숫자를 값으로 저장하는 것을 생각할 수 있습니다

그리고 런타임O (n x n!)을 제외하고는 아무 문제가 없습니다. - WHAT!

따라서 즉시 다른 접근 방식으로 전환해야 합니다. 모든 순열을 계산해야 합니까?

예를 들어 보겠습니다.

input = [1, 2, 3]
solution = [1, 3, 2]

우리는 단순히 큰 숫자를 오른쪽에서 바로 작은 숫자와 교환한다고 말할 수 있습니까?

좋아,하지만 이것은 매번 작동하지 않을 것입니다

input = [1, 3, 2]
solution = [2, 1, 3]

여기에 필요한 유일한 트릭:
우리는 오른쪽에서 시작합니다 - 2보다 약간 작은 인덱스를 찾을 때까지 두 자리를 비교합니다. 즉, 가장 왼쪽 또는 실패한 경우에 도달할 때까지 n-1 <= n을 비교합니다.
[1, 3, 2]에 대해 우리는 i = 0 (1)까지 도달했습니다

이제 우리가 -1에 도달했다면 -> 문제 설명 덕분에 더 큰 숫자를 생성할 수 없으므로 단순히 숫자를 반전하고 반환합니다.

그러나 i >=0 이면 j 보다 큰 숫자를 찾을 때까지 끝에서 다시 시작합니다(예: i ).
2 <= 1
그래서 j = 2 (2)
우리는 i j를 교환[2, 3, 1]
그리고 마지막 단계
i번째 인덱스(i+1) 이후의 모든 숫자를 뒤집습니다.2 [3, 1] -> 2 [1, 3]

구현:

    public static void nextPermutation(int[] nums) {
        int i = nums.length - 2;

        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }

        if (i >= 0) {
            while (nums[j] <= nums[i]) {
                j--;
            }

            swap(nums, i, j);
        }

        reverse(nums, i + 1);
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private static void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

**보너스
좋아하시는 분들이 있기 때문에 python -> 즐기세요 ;)

def next_perm(n):
    i = len(n) - 2
    while i >= 0 and n[i + 1] <= n[i]:
        i -= 1

    if i >= 0:
        j = len(n) - 1
        while n[j] <= n[i]:
            j -= 1

        swap(n, i, j)

    return reverse(n, i + 1)


def swap(n, i, j):
    n[i], n[j] = n[j], n[i]


def reverse(n, from_index):
    res = []
    for i in range(0, from_index):
        res.append(n[i])

    for i in range(len(n) - 1, from_index - 1, -1):
        res.append(n[i])

    return res