C++-Programm: Ordnen Sie die Position von Wörtern in alphabetischer Reihenfolge neu

In diesem Problem wird eine Zeichenfolge als Eingabe angegeben und wir müssen die in der Zeichenfolge vorkommenden Wörter in lexikografischer Reihenfolge sortieren. Dazu weisen wir jedem Wort im String einen Index beginnend bei 1 zu (durch Leerzeichen getrennt) und erhalten die Ausgabe als sortierten Index.

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

Da die Wörter in der Eingabezeichenfolge in lexikografischer Reihenfolge angeordnet wurden, wird die Ausgabe als „1 2“ gedruckt.

Schauen wir uns einige Eingabe-/Ergebnisszenarien an -

Angenommen, alle Wörter in der Eingabezeichenfolge sind gleich, sehen wir uns die Ergebnisse an -

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

Das erhaltene Ergebnis ist die letzte Position des Wortes.

Betrachten wir nun eine Eingabezeichenfolge, die Wörter enthält, die mit demselben Buchstaben beginnen. Die resultierende Ausgabe basiert auf den nachfolgenden Buchstaben des Anfangsbuchstabens.

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

Ein weiteres häufiges Eingabeszenario für diese Methode und die erhaltenen Ergebnisse sind wie folgt: -

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

Hinweis – Die zurückgegebenen Positionen sind die ursprünglichen Positionen dieser Wörter in der Eingabezeichenfolge. Diese Zahlen ändern sich nicht, sobald die Wörter innerhalb der Methode sortiert werden.

Algorithmus

• Diese Methode wird unter Verwendung abstrakter Vektor- und Kartendatentypen durchgeführt.

• Verwenden Sie einen automatischen Iterator, um die Eingabezeichenfolge innerhalb eines Zeichenfolgenbereichs zu durchlaufen.

• Das alphabetische Vertauschen von Wörtern erfolgt, indem diese Elemente an die Rückseite eines Vektordatentyps verschoben werden.

• Sobald die Wörter lexikografisch neu angeordnet sind, werden die ursprünglichen Positionen dieser Wörter in der Zeichenfolge als Ausgabe zurückgegeben.

Beispiel

Lassen Sie uns eine Zeichenfolge haben, die ["articles", "point", "world"] ist, und die Reihenfolge der Zeichenfolgen ist -

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

Wir können jeder Zeichenfolge einen Index zuordnen. Anschließend können wir die Zeichenfolge sortieren und den Index der Karte ausdrucken. Wir können eine sortierte Datenstruktur namens Map in C++ verwenden, um Schlüssel-Wert-Paare zu speichern. Lassen Sie uns unseren Ansatz schnell umsetzen.

#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;
}

Ausgabe

1 2 3

Jetzt lautet die Neuordnung der Zeichenfolge -

“point,”
“articles,”
“world”

Zeitkomplexität - O(n * log n)

Raumkomplexität - O(n)

Fazit

Wir verwenden Karten, um Dinge für uns zu sortieren und abzubilden. Wir können auch eine Hash-Map verwenden, einen Vektor oder ein Array sortieren und dann den Index in der Hash-Map drucken. Die Zeitkomplexität beträgt O(n*log(n)) und die räumliche Komplexität beträgt O(n).

Das obige ist der detaillierte Inhalt vonC++-Programm: Ordnen Sie die Position von Wörtern in alphabetischer Reihenfolge neu. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!