मान लीजिए हमारे पास एक स्ट्रिंग है, हमें वर्णों को आवृत्ति (frequency) के आधार पर क्रमबद्ध करना है। इसलिए यदि स्ट्रिंग "abbbacbcc" जैसी है, तो आउटपुट "bbbbcccaa" होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- v नामक जोड़े की एक सरणी बनाएं, m नामक एक मैप बनाएं
- स्ट्रिंग में सभी वर्णों के लिए,
- m[वर्ण] के मान को 1 से बढ़ाएं
- i := मैप का पहला तत्व
- जब तक मैप में तत्व हैं
- (i.second, i.first) को v में सम्मिलित करें
- और i को अगले तत्व की ओर इंगित करने के लिए बढ़ाएं
- वेक्टर v को क्रमबद्ध करें
- ans := एक खाली स्ट्रिंग
- i := 0 से v के आकार तक
- t := v[i] का पहला तत्व
- जब तक t 0 नहीं है
- ans := ans + v[i] का दूसरा भाग
- t को 1 से घटाएं
- ans लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
#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"); }इनपुट
"abbbacbcc"
आउटपुट
bbbbcccaa
