C++程序：按字母顺序重新排列单词的位置

在这个问题中，一个字符串被作为输入，我们必须按字典顺序对字符串中出现的单词进行排序。为此，我们为字符串中的每个单词（之间用空格区分）分配一个从 1 开始的索引，并以排序索引的形式获得输出。

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

由于输入字符串中的单词已按字典顺序排列，因此输出将打印为“1 2”。

让我们看看一些输入/结果场景 -

假设输入字符串中的所有单词都相同，让我们看看结果 -

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

获得的结果将是单词的最后一个位置。

现在让我们考虑包含以相同字母开头的单词的输入字符串，结果输出将基于起始字母的后继字母。

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

该方法的另一个常见输入场景和获得的结果如下 -

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

注意 - 返回的位置是这些单词在输入字符串中的原始位置。一旦单词在方法内排序，这些数字就不会改变。

算法

• 此方法使用矢量和地图抽象数据类型执行。

• 使用自动迭代器在字符串范围内遍历输入字符串。

• 按字母顺序交换单词是通过将这些元素推到矢量数据类型的后面来完成的。

• 一旦单词按字典顺序重新排列，这些单词在字符串中的原始位置就会作为输出返回。

示例

让我们有一个字符串是[“articles”，“point”，“world”]，字符串的顺序是 -

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

我们可以将每个字符串与索引进行映射。然后我们可以对字符串进行排序，然后打印出映射的索引。我们可以使用 C++ 中的映射（map）这种排序数据结构来存储键值对。让我们快速实施我们的方法。

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

输出

1 2 3

现在字符串的重新排序将是 -

“point,”
“articles,”
“world”

时间复杂度 - O(n * log n)

空间复杂度 - O(n)

结论

我们使用地图来为我们进行排序和映射。我们还可以使用哈希映射，对向量或数组进行排序，然后打印哈希映射中的索引。时间复杂度为 O(n*log(n))，空间复杂度为 O(n)。