Problème
Listez toutes les permutations des caractères de s dans l'ordre lexicographique (l'ordre du dictionnaire). Pour "abc", la liste est abc, acb, bac, bca, cab, cba. Renvoyez le k-ième élément, en comptant à partir de 1. Générer toute la liste est trop lent pour 12 caractères (479 001 600 permutations) : chaque bloc de permutations qui commencent par le même caractère contient (longueur − 1)! éléments, ce qui permet de choisir les caractères un par un.
Implémentez lexicographic_permutation(s, k).
Entrée
s : des caractères distincts, dans un ordre quelconque.
k : la position dans la liste triée, à partir de 1.
Sortie
Renvoyez la k-ième permutation sous forme de chaîne. Les caractères sont comparés selon leur code, donc les chiffres passent avant les majuscules, qui passent avant les minuscules.
Contraintes
1 ≤ s.length ≤ 12 ; tous les caractères de s sont distincts ; 1 ≤ k ≤ s.length!
Exemples
Entrée :
s = "abc"
k = 4
Sortie attendue :
expected = "bca"
Entrée :
std::string s = "abc";
long long k = 4;
Sortie attendue :
std::string expected = "bca";
Entrée :
string s = "abc";
long k = 4;
Sortie attendue :
string expected = "bca";
Explication
La liste est abc, acb, bac, bca, cab, cba, et la quatrième permutation est "bca".
Entrée :
s = "312"
k = 1
Sortie attendue :
expected = "123"
Entrée :
std::string s = "312";
long long k = 1;
Sortie attendue :
std::string expected = "123";
Entrée :
string s = "312";
long k = 1;
Sortie attendue :
string expected = "123";
Explication
La première permutation est celle des caractères triés : "123".
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Commencez par trier les caractères.
Indice 2
Chaque choix du premier caractère couvre (longueur − 1)! permutations, donc diviser k − 1 par ce nombre indique lequel prendre.
Indice 3
Retirez le caractère choisi, gardez le reste de la division et recommencez avec les caractères restants.
Complexité attendue
temps O(n²), espace supplémentaire O(n)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.