C++で最大1つのスワップ操作を使用して次に大きい数

数値nが与えられた場合、結果の数値が数値nより大きくなるように、数値の任意の2桁を交換します。それが不可能な場合は、-1を出力します。例を見てみましょう。

入力

12345

出力

12354

4桁目と5桁目を入れ替えました。1回の入れ替えでより高い数字が得られました。

アルゴリズム

• 数字の桁が降順の場合、数字を形成することはできません。

• 最後の桁よりも小さい数字の右側から桁のインデックスを見つけます。

• 前の桁より大きく、すべての桁より小さい桁のインデックスを見つけます。

• 2桁を入れ替えて、新しい番号を返します。

• 新しい番号を返します。

実装

以下は、C++での上記のアルゴリズムの実装です

#include <bits/stdc++.h>
using namespace std;
string getNextHigherNumber(string num) {
   int len = num.size();
   int firstDigitIndex = -1;
   for (int i = len - 2; i >= 0; i--) {
      if (num[i] < num[len - 1]) {
         firstDigitIndex = i;
         break;
      }
   }
   if (firstDigitIndex == -1) {
      return "-1";
   }
   int secondDigitIndex = -1;
   for (int i = len - 1; i > firstDigitIndex; i--) {
   if (num[i] > num[firstDigitIndex]) {
      if (secondDigitIndex == -1 || num[i] <= num[secondDigitIndex]) {
         secondDigitIndex = i;
         }
      }
   }
   char temp = num[firstDigitIndex];
   num[firstDigitIndex] = num[secondDigitIndex];
   num[secondDigitIndex] = temp;
   return num;
}

int main() {
   string num = "12345";
   cout << "Given number: " << num << endl;
   cout << "Next higher number: " << getNextHigherNumber(num) << endl;
   return 0;
}

出力

上記のコードを実行すると、次の結果が得られます。

Given number: 12345
Next higher number: 12354