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

É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

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

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

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

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

Sortie

1 2 3

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

“point,”
“articles,”
“world”

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!