C++에서 숫자의 다음 정수 순열을 얻는 프로그램

<시간/>

숫자 n이 있다고 가정하고 그 숫자의 다음으로 큰 순열을 찾아야 합니다. n이 이미 가장 큰 순열에 있으면 가장 작은 순열로 회전합니다.

따라서 입력이 n =319와 같으면 출력은 391이 됩니다.

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

함수 makeArray()를 정의하면 x가 필요합니다.
ret 배열 정의
x가 0이 아닌 동안 −
- ret의 끝에 x mod 10 삽입
- x :=x / 10
ret 배열 반전
리턴 렛
Combine() 함수를 정의하면 배열 v가 필요합니다.
ret :=0
v
의 각 요소 i에 대해
- 렛 :=렛 * 10
- 렛 :=렛 + i
리턴 렛
getIndex() 함수를 정의하면 배열 v가 필요합니다.
렛 :=-1
초기화 i :=v의 크기, i>=1일 때 업데이트(i를 1만큼 감소), −
- v[i]> v[i - 1]이면 -
  - 렛 :=나는
  - 루프에서 나오세요
ret가 -1과 같지 않으면 -
- x :=v[ret - 1]
- idx :=렛
- j 초기화의 경우:=ret + 1, j
  - v[j] x이면 -
    - idx :=j
- v[ret - 1] 및 v[idx]
  교환
리턴 렛
주요 방법에서 다음을 수행하십시오 -
배열 정의 v :=makeArray(num)
idx :=getIndex(v)
idx가 -1과 같으면 -
- 배열 v
  정렬
그렇지 않으면
- 배열 v
  정렬
리턴 컴바인(v)

예시

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector<int> makeArray(int x) {
      vector<int> ret;
      while (x) {
         ret.push_back(x % 10);
         x /= 10;
      }
      reverse(ret.begin(), ret.end());
      return ret;
   }
   int combine(vector<int>& v) {
      int ret = 0;
      for (int i : v) {
         ret *= 10;
         ret += i;
      }
      return ret;
   }
   int getIndex(vector& v) {
      int ret = -1;
      for (int i = v.size() - 1; i >= 1; i--) {
         if (v[i] > v[i - 1]) {
            ret = i;
            break;
         }
      }
      if (ret != -1) {
         int x = v[ret - 1];
         int idx = ret;
         for (int j = ret + 1; j < v.size(); j++) {
            if (v[j] < v[idx] && v[j] > x) {
               idx = j;
            }
         }
         swap(v[ret - 1], v[idx]);
      }
      return ret;
   }
   int solve(int num) {
      vector<int> v = makeArray(num);
      int idx = getIndex(v);
      if(idx == -1) {
         sort(v.begin(), v.end());
      }
      else {
         sort(v.begin() + idx, v.end());
      }
      return combine(v);
   }
};
int solve(int n) {
   return (new Solution())->solve(n);
}
int main(){
   int n = 319;
   cout << solve(n);
}