Maison > Article > développement back-end > 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
À 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
À 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.
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.
#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; }
The next number or permutation for the given number is: 123
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.
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!