Programme C++ : réorganiser la position des mots par ordre alphabétique-C++-php.cn

Programme C++ : réorganiser la position des mots par ordre alphabétique

Dans ce problème, une chaîne est donnée en entrée et nous devons trier les mots apparaissant dans la chaîne par ordre lexicographique. Pour ce faire, nous attribuons un index commençant à 1 à chaque mot de la chaîne (séparés par des espaces) et obtenons le résultat sous forme d'index trié.

String = {“Hello”, “World”} “Hello” = 1 “World” = 2

Copier après la connexion

Étant donné que les mots de la chaîne d'entrée ont été classés par ordre lexicographique, le résultat sera imprimé sous la forme "1 2".

Regardons quelques scénarios d'entrée/résultat -

En supposant que tous les mots de la chaîne d'entrée sont identiques, voyons les résultats -

Input: {“hello”, “hello”, “hello”} Result: 3

Copier après la connexion

Le résultat obtenu sera la dernière position du mot.

Considérons maintenant une chaîne d'entrée contenant des mots commençant par la même lettre, la sortie résultante sera basée sur les lettres suivantes de la lettre de départ.

Input: {“Title”, “Tutorial”, “Truth”} Result: 1 3 2

Copier après la connexion

Un autre scénario d'entrée courant pour cette méthode et les résultats obtenus sont les suivants -

Input: {“Welcome”, “To”, “Tutorialspoint”} Result: 2 3 1

Copier après la connexion

Remarque- Les positions renvoyées sont les positions d'origine de ces mots dans la chaîne d'entrée. Ces nombres ne changent pas une fois les mots triés dans la méthode.

Algorithme

Cette méthode est exécutée en utilisant des types de données abstraites vectorielles et cartographiques.
Utilisez un itérateur automatique pour parcourir la chaîne d'entrée dans une plage de chaînes.
L'échange de mots par ordre alphabétique se fait en poussant ces éléments à l'arrière d'un type de données vectorielles.
Une fois les mots réorganisés lexicographiquement, les positions d'origine de ces mots dans la chaîne sont renvoyées en sortie.

Exemple

Prenons une chaîne qui est ["articles", "point", "world"], et l'ordre des chaînes est -

“articles”: 1 “point”: 2 “world”: 3

Copier après la connexion

Nous pouvons mapper chaque chaîne avec un index. Nous pouvons ensuite trier la chaîne et imprimer l'index de la carte. Nous pouvons utiliser une carte, une structure de données triée en C++, pour stocker des paires clé-valeur. Mettons rapidement en œuvre notre approche.

#include  #include  #include  using namespace std; vector solve(vector& arr) { map mp; int index = 1; for(string s : arr) mp[s] = index++; vector res; for(auto it : mp) res.push_back(it.second); return res; } int main() { vector arr = {"articles", "point", "world"}; vector res = solve(arr); for(int i : res) cout << i << " "; return 0; }

Copier après la connexion

Sortie

1 2 3

Copier après la connexion

Maintenant, la réorganisation de la chaîne sera -

“point,” “articles,” “world”

Copier après la connexion

Complexité temporelle- O(n * log n)

Complexité spatiale- O(n)

Conclusion

Nous utilisons des cartes pour trier et cartographier les choses pour nous. Nous pouvons également utiliser une carte de hachage, trier un vecteur ou un tableau, puis imprimer l'index dans la carte de hachage. La complexité temporelle est O(n*log(n)) et la complexité spatiale 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!