다음 큰 순열

(2020 년 11 월 26 일)

세 가지 색상의 순열

순열의 의미를 먼저 이해하겠습니다. Wikipedia에서 가져온 정의는 “ In 수학 , a 순열 set 은 간단히 말해서 구성원을 순서 로 배열 한 것입니다. em> 또는 선형 순서 또는 세트가 이미 주문 된 경우 , 요소의 재배치. “순열”이라는 단어는 또한 정렬 된 집합의 선형 순서를 변경하는 행위 또는 프로세스를 나타냅니다.

정의에서 말했듯이 순열은 주어진 개체 집합을 다시 정렬하는 것을 의미합니다. 가능한 모든 주문. 위의 다이어그램에서 볼 수 있듯이 세 가지 색상을 6 가지 방식으로 배열 할 수 있습니다. {RGB, RBG, GRB, GBR, BRG, BGR}.

가능한 배열 수를 계산하는 수학 공식 n 개의 다른 객체에 대해 n !, 여기서 n! = n * (n-1) * (n-2) *… * 1

주어진 시퀀스의 모든 순열을 체계적으로 생성하는 방법에는 여러 가지가 있습니다. 하나의 고전적인 알고리즘은 사전 / 사전 / 알파벳 순서로 다음 순열을 찾는 것을 기반으로합니다. 그것을 문자열이라고 부르고, 우리는 다음 사전 식 알파벳 세트 또는 다음 사전 식 큰 문자열 또는 현재 문자열과 동일한 알파벳 세트를 가진 현재 문자열 다음 사전에서 다음에 올 문자열을 찾아야합니다.

더 잘 이해하기 위해 숫자의 예를 들어 보겠습니다.

Number = [4,5,2,6,7,3,1]
다음으로 큰 숫자는 = [4,5,2, 7,1,3,6 ]

브 루트 포스

첫 번째로 떠오르는 것은 주어진 숫자의 모든 순열을 찾고 현재 숫자보다 큰 순열 중 가장 작은 것이 답이 될 것입니다. 위에서 보았 듯이 n이 있습니다! 가능성 (n = 숫자의 자릿수), 모든 자릿수를 고유 한 것으로 간주하므로 주어진 숫자에 대한 모든 순열을 계속 찾으면 계산하는 데 O (n!) 시간이 걸립니다. n이 큰 숫자 인 경우 시간이 너무 복잡합니다.

최적화

이 문제를 개선 할 수있는 방법을 생각해야합니다. 주의 깊게 관찰하면 더 작은 숫자 집합에 대해 패턴을 볼 수 있습니다. 몇 가지 예를 들어 보겠습니다.

[2,1,3] = 다음으로 큰 숫자는 231입니다.
[1,1,5] = 다음으로 큰 숫자는 151입니다.
[2,3 , 5,4] = 다음으로 큰 숫자는 2435입니다.
[3,2,1] = 가능한 모든 순열에서 현재 숫자보다 큰 숫자를 만들 수 없습니다.

위에서 얻은 교훈 관찰 :

사례 1 : [3,2,1]

여기서 우리는 오른쪽 끝에서 이동하기 시작하고 첫 번째 감소하는 요소를 찾으려고합니다. 오른쪽에서 자신보다 큰 요소입니다.

사례 1 : 다음으로 큰 요소는 비 증가 순서로 가능

케이스 2 : [2,3,5,4]

index = 1, 오른쪽 끝에서 첫 번째 감소하는 요소의 색인
에서 3보다 큰 다음으로 큰 요소를 찾습니다. i = 1의 오른쪽, 숫자 [i]
이제 i = 1 이후의 나머지 요소를 오름차순으로 정렬하여 가장 작은 요소를 만듭니다. 이미 증가하지 않는 순서로 정렬되어 있으므로 i = 1 이후의 요소를 간단히 뒤집을 수 있습니다.

이 그래프는 4와 5를 스와핑 할 때 8부터 시작하는 시퀀스, 즉 86432가 여전히 증가하지 않는 순서로 정렬되어 있음을 증명하며 첫 번째 감소하는 요소를 그보다 더 큰 요소로 대체하는 것이 매우 분명합니다. 따라서 증가하지 않는 순서를 유지합니다.

여기서 살펴볼 수있는 또 하나의 관찰은 인덱스 j = i + 1에서 오른쪽으로 다음으로 큰 요소를 검색하는 동안 인덱스 j에서 검색을 중지 할 수 있다는 것입니다. nums [j]가 nums [i]보다 작거나 같을 때, 해당 인덱스 뒤의 요소는 절대 b 일 수 없습니다. e가 nums [i]보다 큽니다.

코드 스 니펫

다음 코드에서 다음으로 큰 순열이 불가능합니다. 가능한 가장 작은 순열로 변환합니다.

복잡성 분석

시간 복잡성 = O (n) { 최악의 경우 첫 번째 감소 요소를 찾으려면 [1,5,4,3,2]} + O (n) {오른쪽의 나머지 하위 배열에서 다음으로 큰 숫자를 찾으려면} + O (1) {첫 번째 감소하는 요소를 다음으로 큰 요소로 교체} + O (n / 2) {하위 배열을 i + 1에서 len으로 뒤집어 오름차순으로 정렬} = O (n)

추가 공간이 필요하지 않으므로 추가 공간이 필요하지 않습니다. .
따라서 공간 복잡성 : O (1)

이 기사에 시간을 할애 해 주셔서 감사합니다. 도움이되었고 명확한 통찰력을 얻으 셨기를 바랍니다.

아직 궁금한 점이 있으면 언제든지 답변 해주세요. 도움이된다면 동료들과 공유하십시오. 당신의 박수는 내가 더 많은 블로그를 작성하도록 동기를 부여합니다! 🙂