C++で最大1つのスワップ操作を使用して最小数を形成します

この問題では、正の整数が与えられます。私たちの仕事は、多くても1回のスワップ操作を使用して少数を形成するプログラムを作成することです。

既存の番号の桁を使用して新しい番号を作成します。形成される最小の数字は、既存の数字から1桁だけ交換できます。

問題を理解するために例を見てみましょう

Input: n = 63519
Output: 36519

ソリューションアプローチ

この問題を解決する1つの方法は、指定された数字の数字のペアを交換することによって作成されたすべての数字を見つけることです。これらの交換されたすべての桁番号のうち、最小のものが返されます。このために、数値を文字列に変換して位置を入れ替えます。

例

ソリューションの動作を説明するプログラム

#include <iostream>
using namespace std;

int findSmallestNumSwapDig(int N){

   string strNum = to_string(N);
   string temp = strNum;
   for (int i = 0; i < strNum.size(); i++) {
      for (int j = i + 1; j < strNum.size(); j++) {
         swap(strNum[i], strNum[j]);
         if (stoi(strNum) < stoi(temp))
            temp = strNum;
         swap(strNum[i], strNum[j]);
      }
   }
   return stoi(temp);
}
int main(){
   int num = 792156;
   cout<<"The number is "<<num<<endl;
   cout<<"The smallest number created by swapping one digit is "<<findSmallestNumSwapDig(num) << endl;
   return 0;
}

出力

The number is 792156
The smallest number created by swapping one digit is192756

別のアプローチ

この問題を解決するもう1つのアプローチは、追加の補助配列aux[]を使用することです。この配列は、現在のインデックスの右側にある最小の桁のインデックス（大きい方のインデックス）を格納するために使用されます。つまり、aux [i]は、数値の桁の右側にある最小の桁のインデックスです。そのような数字が存在しない場合は、aux [i]=-1を初期化します。ここで、インデックス0からn-1までの数値をトラバースし、現在の値よりも小さいaux[]配列内の数値を見つけます。インデックス0の値については、ゼロ以外の要素を確認します。0が発生した場合は、値を破棄します。要素が見つかった場合は、arr[i]とarr[aux[i]]を入れ替えます。 作成した番号を返します。

例

ソリューションの動作を説明するプログラム

#include <bits/stdc++.h>
using namespace std;

int findSmallestNumSwapDig(int N){

   string num = to_string(N);
   int n = num.size();
   int auxArr[n], right;
   auxArr[n - 1] = -1;
   right = n - 1;
   for (int i = n - 2; i >= 1; i--) {
      if (num[i] >= num[right])
         auxArr[i] = right;
      else {
         if (num[i] == num[i + 1])
            auxArr[i] = right;
         else {
            auxArr[i] = -1;
            right = i;
         }
      }
   }
   int small = -1;
   for (int i = 1; i < n; i++)
   if (num[i] != '0') {
      if (small == -1) {
         if (num[i] < num[0])
            small = i;
      }
      else if (num[i] <= num[small])
            small = i;
   }
   if (small != -1)
      swap(num[0], num[small]);
   else {
      for (int i = 1; i < n; i++) {
         if (auxArr[i] != -1 && num[i] != num[auxArr[i]]) {
            swap(num[i], num[auxArr[i]]);
            break;
         }
      }
   }
   return stoi(num);
}
int main(){
   int num = 792156;
   cout<<"The number is "<<num<<endl;
   cout<<"The smallest number created by swapping one digit is" <<findSmallestNumSwapDig(num)<< endl;
      return 0;
}

出力

The number is 792156
The smallest number created by swapping one digit is192756