C++で同じ数字のセットを使用してNよりも小さい最大数を検索します

この問題では、数値を表す文字列Nが与えられます。私たちのタスクは、同じ数字のセットでNよりも小さい最大数を見つけることです。

問題の説明： Nよりも小さい最大の数である、与えられた数のすべての桁を使用して数を見つける必要があります。

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

入力： N =“ 54314”

出力： 54341

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

この問題の簡単な解決策は、移動できる数字の桁を見つけて、最大の小さい数字を見つけることです。さて、目的を解決するためには、その数は正しい成功よりも大きいはずです。

このために、数字の形式を右から左にトラバースして、最後の要素よりも大きい要素を見つけます。

次に、右側のサブ配列で最大の要素を見つけて、それを現在の要素に置き換えます。ソート後、サブ配列は降順です。これはあなたの最大の小さな要素になります。

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

例

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

void calcGreatestSmallerElement(string N, int size) {
   
   int i, j;
   for (i = size - 1; i > 0; i--)
      if (N[i] < N[i - 1])
         break;

   if (i == 0) {
      cout << "Previous number is not possible";
      return;
   }

   int x = N[i - 1], greatest = i;
   for (j = i; j < size; j++)
      if (N[j] < x && N[j] > N[greatest])
         greatest = j;

   swap(N[greatest], N[i - 1]);
   sort(N.begin() + i, N.begin() + size, greater<char>());

   cout<<"The Greatest smaller number with same set of digits is "<<N;

   return;
}

int main() {
   
   string N = "654232";
   int size = N.length();
   cout<<"The number is "<<N<<endl;
   calcGreatestSmallerElement(N, size);

   return 0;
}

出力

The number is 654232
The Greatest smaller number with same set of digits is 654223