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++ 中使用映射，一种排序的数据结构来存储键值对。让我们快速实现我们的方法。

#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)。

更新于： 2022年8月10日

471 次浏览

开启你的 职业生涯

完成课程获得认证

立即开始
广告