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

Prateek Jangid

更新於： 2022年8月10日

471 次瀏覽

開啟你的 職業生涯

完成課程獲得認證

立即開始