মান লইয়া আমরা একটি স্ট্যাক কনস্ট্রাক্ট করতে চাই নামক FrequencyStack, যাতে দুটি ফাংশন থাকে:
append(x), এটি ভ্যালু x স্টাকে অ্যাপেন্ড বা পুশ করবে।pop(), এটি স্ট্যাক থেকে সবচেয়ে বেশি ফ্রিকোয়েন্সি বিশিষ্ট এলিমেন্ট রিমুভ করবে এবং রিটার্ন করবে। যদি একাধিক এলিমেন্ট একই ফ্রিকোয়েন্সি থাকে, তবে স্ট্যাকের টপের কাছাকাছি এলিমেন্টটি রিমুভ ও রিটার্ন করা হবে।
তবে, যদি ইনপুট হয় 7, 9, 7, 9, 6, 7 অ্যাপেন্ড করুন, তারপর চারবার pop অপারেশন করুন, তবে আউটপুট হবে 7, 9, 7, 6 যথাক্রমে।
এটি সমাধান করতে, আমরা এই ধাপগুলো ফলো করব:
- একটি map cnt ডিফাইন করুন
- একটি map sts ডিফাইন করুন
- maxFreq := 0
- append() ফাংশন ডিফাইন করুন, এটি x নেবে:
- cnt[x]++
- maxFreq := max(maxFreq, cnt[x])
- x কে sts[cnt[x]]-এ পুশ করুন
- pop() ফাংশন ডিফাইন করুন:
- maxKey := maxFreq
- x := sts[maxKey]-এর টপ এলিমেন্ট
- sts[maxKey]-এর টপ ডিলিট করুন
- যদি sts[maxKey]-এর সাইজ ০ হয়, তবে maxKey sts থেকে ডিলিট করুন এবং maxFreq--
- cnt[x]--
- x রিটার্ন করুন
বेहतर বোঝার জন্য ইমপ্লিমেন্টেশন দেখুন:
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class FreqStack {
public:
unordered_map <int ,int > cnt;
unordered_map <int, stack <int> > sts;
int maxFreq = 0;
FreqStack() {
maxFreq = 0;
cnt.clear();
sts.clear();
}
void append(int x) {
cnt[x]++;
maxFreq = max(maxFreq, cnt[x]);
sts[cnt[x]].push(x);
}
int pop() {
int maxKey = maxFreq;
int x = sts[maxKey].top();
sts[maxKey].pop();
if(sts[maxKey].size() == 0){
sts.erase(maxKey);
maxFreq--;
}
cnt[x]--;
return x;
}
};
main(){
FreqStack ob;
ob.append(7);
ob.append(9);
ob.append(7);
ob.append(9);
ob.append(6);
ob.append(7);
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
}
ইনপুট
ob.append(7); ob.append(9); ob.append(7); ob.append(9); ob.append(6); ob.append(7); cout << (ob.pop()) << endl; cout << (ob.pop()) << endl; cout << (ob.pop()) << endl; cout << (ob.pop()) << endl;
আউটপুট
7 9 7 6
