Giả sử chúng ta có một chuỗi, chúng ta phải sắp xếp các ký tự dựa trên tần suất. Vì vậy, nếu chuỗi giống như “abbbacbcc”, thì đầu ra sẽ là “bbbbcccaa”
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- tạo một mảng các cặp được gọi là v, tạo một bản đồ m
- cho tất cả các ký tự trong chuỗi,
- tăng giá trị của m [ký tự] lên 1
- i:=phần tử đầu tiên của bản đồ
- trong khi bản đồ có các phần tử
- chèn (i.second, i.first) vào v
- và tăng i để trỏ đến phần tử tiếp theo
- sắp xếp vectơ v
- ans:=một chuỗi trống
- for i:=0 to size of v
- t:=phần tử đầu tiên của v [i]
- trong khi t không phải là 0
- ans:=ans + phần thứ hai của v [i]
- giảm t đi 1
- trả lại ans
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
static bool cmp(pair <int, char> a, pair <int, char> b){
return a.first < b.first;
}
string frequencySort(string s) {
vector < pair <int, char> > v;
map <char, int> m;
for(int i = 0; i < s.size(); i++){
m[s[i]]++;
}
map <char, int> :: iterator i = m.begin();
while(i != m.end()){
v.push_back({i->second, i->first});
i++;
}
sort(v.rbegin(), v.rend(), cmp);
string ans = "";
for(int i = 0; i < v.size(); i++){
int t = v[i].first;
while(t--)ans += v[i].second;
}
return ans;
}
};
main(){
Solution ob;
cout << ob.frequencySort("abbbacbcc");
} Đầu vào
"abbbacbcc"
Đầu ra
bbbbcccaa