C++で数値の次の整数順列を取得するプログラム

数nがあるとすると、その数字の次に大きな順列を見つける必要があります。 nがすでに最大の順列にある場合は、最小の順列まで回転させます。

したがって、入力がn =319の場合、出力は391になります。

これを解決するには、次の手順に従います-

• 関数makeArray（）を定義します。これにはxが必要です

• 配列retを定義する

• xがゼロ以外の場合、-

  を実行します。

  • retの最後にxmod10を挿入します

  • x：=x / 10

• 配列を逆にするret

• retを返す

• 関数combine（）を定義します。これは配列vを取ります

• ret：=0

• vの各要素iについて

  • ret：=ret * 10

  • ret：=ret + i

• retを返す

• 関数getIndex（）を定義します。これには、配列vが必要です。

• ret：=-1

• 初期化i：=vのサイズ、i> =1の場合、更新（iを1つ減らす）、実行-

  • v [i]> v [i-1]の場合、-

    • ret：=i

    • ループから出てきます

• retが-1に等しくない場合、-

  • x：=v [ret-1]

  • idx：=ret

  • 初期化j：=ret + 1の場合、j

    • v [j]xの場合、-

      • idx：=j

  • v[ret-1]とv[idx]

    を交換します

• retを返す

• メインの方法から、次のようにします-

• 配列を定義するv：=makeArray（num）

• idx：=getIndex（v）

• idxが-1と同じ場合、-

  • 配列を並べ替えるv

• それ以外の場合

  • 配列を並べ替えるv

• リターンcombine（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);
}

入力

319

出力

391