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

以上是C++程式：按字母順序重新排列單字的位置的詳細內容。更多資訊請關注PHP中文網其他相關文章！