En fonction de la priorité des nombres, la traduction est la suivante : Nombre suivant plus grand en fonction de la priorité des nombres

Dans le système numérique normal, 0 est le plus petit nombre et 9 est le plus grand nombre. Dans ce problème, nous obtiendrons une liste de longueur 10, de l'index 0 à l'index 9 représente un nombre qui représente la priorité de ce numéro, la liste sera par ordre croissant, ce qui signifie que le numéro apparaissant au dernier index a la priorité la plus élevée. Nous recevrons également un nombre et nous devons trouver le prochain nombre légèrement supérieur au nombre actuel.

Input 1: 
Given number = “123”
Given array = { 9, 2, 3, 6, 8, 1, 0, 5, 4, 7}
Output: 132

Explication

À partir du tableau de priorités donné, nous pouvons voir que 1 a une priorité supérieure à 2 et 3. 3 a une priorité plus élevée que 2. Donc, si la prochaine permutation d'un nombre donné sera obtenue en échangeant 2 et 3.

Input 2:
Given number = 132
Given array = { 9, 2, 3, 6, 8, 1, 0, 5, 4, 7}
Output: 132

Explication

À partir du tableau de priorités donné, nous pouvons voir que la priorité de 1 est supérieure à celle de 2 et de 3. La priorité de 3 est supérieure à celle de 2. Ainsi, il n'y aura pas de prochaine permutation disponible.

Méthode

Dans cette approche, nous utiliserons le concept de bibliothèque de modèles standard (STL) fourni par le langage de programmation C++ pour obtenir la permutation suivante −

.

• Tout d'abord, nous obtiendrons le numéro du numéro suivant, ainsi qu'un tableau représentant la priorité des numéros par ordre croissant.

• Nous appellerons la fonction prédéfinie pour trouver le prochain nombre supérieur au nombre actuellement donné.

• Nous définirons une fonction qui prend le paramètre donné en nombre et en tableau

.

• Nous définirons un tableau global et stockerons la priorité de chaque chiffre extrait du tableau donné pour l'utiliser plus tard

.

• Nous allons convertir le nombre donné en chaîne afin d'y appliquer la prochaine fonction de permutation.

• Nous définirons une fonction personnalisée qui sera utilisée pour comparer les caractères de la chaîne dans la prochaine fonction de permutation du stl

.

• Après avoir obtenu la permutation suivante, nous convertirons la chaîne en entier et inversement.

La traduction chinoise de

Exemple

est :

Exemple

#include <bits/stdc++.h>
using namespace std;
// priority array or array in which the priority of each digit will be stored 
int prio[10];
// defining the compare function 
bool compare(char& a, char& b){
   return prio[a-'0'] < prio[b-'0'];
}
// function to get the next permuatation 
int nextNum(int n, int arr[]){
   for(int i=0; i<10; i++){
      prio[arr[i]] = i;
   }
   // converting the given number into string 
   string str = to_string(n);
   // calling the next permuatation stl function for the given string we will compare by custom function 
   bool cur = next_permutation(str.begin(),str.end(),compare);
   if(cur == false){
      // indicating the next permutation does not exist 
      return n;
   }
   n = stoi(str); // converting string back to number 
   return n;
}
int main(){
   int n = 312; // the given number 
   int arr[] = {9, 2, 3, 6, 8, 1, 0, 5, 4, 7}; // given array
   cout<<"The next number or permutation for the given number is: "<<nextNum(n, arr);
   return 0;
}

Sortie

The next number or permutation for the given number is: 123

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N), où N est le nombre de chiffres dans le nombre donné

.

La complexité spatiale du code ci-dessus est O(N) car nous créons une nouvelle chaîne pour utiliser la fonction de permutation suivante.

Remarque : Si le nombre actuel est le plus grand nombre parmi toutes les permutations, alors la fonction de permutation suivante renverra false et nous renverrons le même nombre car la permutation suivante n'existe pas.

Conclusion

Dans ce tutoriel, nous avons implémenté un code pour trouver le prochain nombre supérieur au nombre actuel, mais la priorité des nombres n'est pas dans l'ordre de 0 à 9 mais est donnée dans un tableau séparé. Nous avons utilisé la fonction STL next_permutation et une fonction personnalisée pour obtenir le numéro suivant en fonction de la nouvelle priorité. La complexité temporelle et spatiale du code ci-dessus est O (nombre de chiffres).

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!