Étant donné une chaîne binaire S de taille (N-1), la tâche est de trouver la plus petite permutation lexicographique P du premier N nombres naturels tels que pour chaque indice je, si S[i] équivaut à ‘0‘ alors P[i + 1] doit être supérieur à P[i] et si S[i] équivaut à ‘1‘ alors P[i + 1] doit être inférieur à P[i].
Exemples:
Saisir: N = 7, S = 100101
Sortir: 2 1 3 5 4 7 6
Explication:
Considérez la permutation comme {2, 1, 3, 5, 4, 7, 6} qui satisfait les critères donnés comme :
Pour l’indice 0, S[0] = 1, P[1] < P[0], soit 1 < 2
Pour l’indice 1, S[1] = 0, P[2] < P[1], soit 3 > 1
Pour l’indice 2, S[2] = 0, P[3] < P[2], soit 5 > 3
Pour l’indice 3, S[3] = 1, P[4] < P[3], soit 4 < 5
Pour l’indice 4, S[4] = 0, P[5] < P[4], soit 7 > 4
Pour l’indice 5, S[5] = 1, P[6] < P[5], soit 6 < 7
Saisir: N = 4, S = 000
Sortir: 1 2 3 4
Approcher: Le problème donné peut être résolu en utilisant l’approche gloutonne en utilisant autant que possible des nombres plus petits à des indices inférieurs pour créer les permutations lexicographiquement les plus petites. Suivez les étapes ci-dessous pour résoudre le problème :
- Initialiser un tableau, disons ans[] de taille N qui stocke la permutation résultante.
- Parcourir la chaîne donnée S et effectuez les étapes suivantes :
- Si la valeur de S[i] équivaut à ‘0‘ puis attribuez le numéro supérieur au dernier numéro attribué.
- Sinon, attribuez le plus petit nombre qui est plus grand que tous les nombres actuellement utilisés.
- Après avoir terminé les étapes ci-dessus, imprimez la permutation résultante formée dans le tableau ans[].
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
Table des matières
C++
|
#include en utilisant l’espace de noms std ; void constructPermutation(string S, int N) { int ans[N]; ans[0] = 1 ; pour (int i = 1; i < N; ++i) { si (S[i – 1] == ‘0’) { ans[i] = je + 1; } autre { ans[i] = ans[i – 1]; } pour (int j = 0; j < i; ++j) { si (et[j] >= ans[i]) { ans[j]++ ; } } } pour (int i = 0; i < N; i++) { cout << ans[i]; si (i != N – 1) { cout << " "; } } } int main() { chaîne S = « 100101 » ; constructPermutation(S, S.length() + 1); renvoie 0 ; } |
Complexité temporelle : O(N2)
Espace auxiliaire : AU)
Attention lecteur ! N’arrêtez pas d’apprendre maintenant. Obtenez tous les concepts importants de DSA avec le Cours auto-rythmé DSA à un prix adapté aux étudiants et devenez prêt pour l’industrie. Pour compléter votre préparation de l’apprentissage d’une langue à DS Algo et bien d’autres, veuillez vous référer Cours complet de préparation aux entretiens.
Au cas où vous souhaiteriez assister cours en direct avec des experts, veuillez vous référer Cours en direct DSA pour les professionnels en activité et Programmation compétitive en direct pour les étudiants.
