Program C++: susun semula kedudukan perkataan dalam susunan abjad

Dalam masalah ini, rentetan diberikan sebagai input dan kita perlu mengisih perkataan yang terdapat dalam rentetan dalam susunan leksikografi. Untuk melakukan ini, kami menetapkan indeks bermula dari 1 kepada setiap perkataan dalam rentetan (dipisahkan oleh ruang) dan mendapatkan output sebagai indeks yang diisih.

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

Memandangkan perkataan dalam rentetan input telah disusun dalam susunan leksikografi, output akan dicetak sebagai "1 2".

Mari lihat beberapa senario input/hasil -

Dengan mengandaikan semua perkataan dalam rentetan input adalah sama, mari lihat hasilnya -

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

Hasil yang diperolehi akan menjadi kedudukan terakhir perkataan.

Sekarang mari kita pertimbangkan rentetan input yang mengandungi perkataan yang bermula dengan huruf yang sama, output yang terhasil akan berdasarkan huruf seterusnya bagi huruf permulaan.

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

Satu lagi senario input biasa untuk kaedah ini dan keputusan yang diperoleh adalah seperti berikut -

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

Nota - Kedudukan yang dikembalikan ialah kedudukan asal perkataan ini dalam rentetan input. Nombor ini tidak berubah setelah perkataan diisih dalam kaedah.

Algoritma

• Kaedah ini dilakukan menggunakan vektor dan jenis data abstrak peta.

• Gunakan lelaran automatik untuk melintasi rentetan input dalam julat rentetan.

• Pertukaran abjad perkataan dilakukan dengan menolak elemen ini ke belakang jenis data vektor.

• Setelah perkataan disusun semula secara leksikografi, kedudukan asal perkataan tersebut dalam rentetan dikembalikan sebagai output.

Contoh

Mari kita mempunyai rentetan iaitu ["artikel", "titik", "dunia"], dan susunan rentetan itu ialah -

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

Kita boleh memetakan setiap rentetan dengan indeks. Kami kemudiannya boleh mengisih rentetan dan mencetak indeks peta. Kita boleh menggunakan peta, struktur data yang diisih dalam C++, untuk menyimpan pasangan nilai kunci. Mari kita cepat melaksanakan pendekatan kita.

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

Output

1 2 3

Kini susunan semula rentetan akan menjadi -

“point,”
“articles,”
“world”

Kerumitan masa - O(n * log n)

Kerumitan ruang - O(n)

KESIMPULAN

Kami menggunakan peta untuk mengisih dan memetakan sesuatu untuk kami. Kita juga boleh menggunakan peta cincang, mengisih vektor atau tatasusunan, dan kemudian mencetak indeks dalam peta cincang. Kerumitan masa ialah O(n*log(n)) dan kerumitan ruang ialah O(n).

Atas ialah kandungan terperinci Program C++: susun semula kedudukan perkataan dalam susunan abjad. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!