Maison >développement back-end >C++ >Trouver le plus petit nombre formé en insérant les nombres donnés
Insérer un numéro dans un numéro donné signifie ajouter un nouveau numéro au numéro donné, soit avant, après ou au milieu du numéro. On nous a donné un nombre et un nombre et nous devons ajouter ce nombre au nombre de la manière la plus petite possible. Pour faciliter l'opération d'insertion, nous allons convertir le nombre en chaîne. De plus, le nombre donné peut également être négatif, nous devons donc tenir compte de ce cas.
Given number: 124 Given digit: 3 Output: 1234
Explication − Nous avons quatre endroits où nous pouvons additionner le nombre donné et le résultat peut être 3124, 1324, 1234, 1243. Des quatre, l’avant-dernier est le plus petit.
La traduction chinoise deGiven number: -124 Given digit: 3 Output: -3124
Explication − Nous avons quatre endroits où nous pouvons ajouter le nombre donné et le résultat peut être -3124, -1324, -1234, -1243. Des quatre, le premier est le plus petit.
La traduction chinoise deMaintenant que nous avons vu l'exemple, regardons les étapes que nous allons effectuer pour résoudre le problème -
Tout d'abord, nous vérifierons si le nombre actuel est positif ou négatif.
Si le nombre actuel est négatif, nous le marquerons comme variable négative et rendrons le nombre actuel positif.
Après cela, nous convertirons le nombre actuel en chaîne et appellerons la fonction selon que le nombre actuel est positif ou négatif.
Dans ces fonctions, nous essaierons d'ajuster le nombre à chaque position et vérifierons si le nombre actuel est plus petit ou plus grand en fonction de nombres positifs ou négatifs.
Si le nombre actuel est positif, nous essaierons de trouver le plus petit nombre et de le renvoyer.
Sinon, on trouve le plus grand nombre et on le renvoie en multipliant par -1.
#include <bits/stdc++.h> using namespace std; int findMin(string str, int d){ string ans = str + to_string(d); // variable to store the answer // traversing over the string for(int i=0; i<= str.size(); i++){ ans = min(ans, str.substr(0,i) + to_string(d) + str.substr(i)); } return stoi(ans); } int findMax(string str, int d){ string ans = str + to_string(d); // variable to store the answer // traversing over the string for(int i=0; i<= str.size(); i++){ ans = max(ans, str.substr(0,i) + to_string(d) + str.substr(i)); } return stoi(ans); } int minimumNumber(int n, int d){ // checking for the negative number int isNeg = 1; if(n < 0){ n *= -1; isNeg = -1; } // converting the current number to string string str = to_string(n); if(isNeg == 1){ return findMin(str,d); } else{ return -1*findMax(str,d); } } int main(){ int n = -124; // given number int d = 3; // given digit // calling to the function n = minimumNumber(n, d); cout<<"The minimum number after adding the new digit is "<<n<<endl; return 0; }
The minimum number after adding the new digit is -3124
La complexité temporelle du code ci-dessus est O(N*N), où N est le nombre de chiffres dans le nombre donné.
La complexité spatiale du code ci-dessus est O(N), où N est le nombre de chiffres dans le nombre donné.
Dans la méthode précédente, nous avons vérifié chaque nombre, trouvé le premier nombre supérieur au nombre donné, puis l'avons ajouté et renvoyé lui-même, ce qui est une méthode efficace. Pour les nombres négatifs, trouvez le plus petit nombre, ajoutez-le et renvoyez-le.
Voyons le code−
La traduction chinoise de#include <bits/stdc++.h> using namespace std; int findMin(string str, int d){ // traversing over the string for(int i=0; i<= str.size(); i++){ if(str[i]-'0' > d){ return stoi(str.substr(0,i) + to_string(d) + str.substr(i)); } } return stoi(str + to_string(d)); } int findMax(string str, int d){ // traversing over the string for(int i=0; i<= str.size(); i++){ if(str[i]-'0' < d){ return stoi(str.substr(0,i) + to_string(d) + str.substr(i)); } } return stoi(str + to_string(d)); } int minimumNumber(int n, int d){ // checking for the negative number int isNeg = 1; if(n < 0){ n *= -1; isNeg = -1; } // converting the current number to string string str = to_string(n); if(isNeg == 1){ return findMin(str,d); } else{ return -1*findMax(str,d); } } int main(){ int n = 124; // given number int d = 3; // given digit // calling to the function n = minimumNumber(n, d); cout<<"The minimum number after adding the new digit is "<<n<<endl; return 0; }
The minimum number after adding the new digit is 1234
La complexité temporelle du code ci-dessus est O(N), où N est le nombre de chiffres du nombre donné.
La complexité spatiale du code ci-dessus est O(N), où N est le nombre de chiffres dans le nombre donné.
Dans ce tutoriel, nous avons implémenté une méthode pour insérer des nombres dans un nombre donné, c'est-à-dire ajouter un nouveau nombre donné avant, après ou entre les nombres. Nous avons vu deux méthodes, l'une avec une complexité temporelle de O(N*N) et l'autre avec une complexité temporelle de O(N). La complexité spatiale des deux méthodes est O(N).
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!