परिचय
मान लीजिए हम एक स्टैक बनाना चाहते हैं जिसे FrequencyStack कहा जाता है। हमारे FrequencyStack में दो फंक्शन्स हैं:
- append(x), यह मान x को स्टैक पर जोड़ता या पुश करता है।
- pop(), यह स्टैक में सबसे अधिक फ्रीक्वेंट (frequent) एलिमेंट को हटाता है और वापस करता है। यदि एक ही फ्रीक्वेंसी के एक से अधिक एलिमेंट्स हैं, तो स्टैक के शीर्ष के निकटतम एलिमेंट को हटाया और वापस किया जाता है।
तो, यदि इनपुट 7, 9, 7, 9, 6, 7 जैसे एलिमेंट्स को जोड़ना है, फिर चार बार pop ऑपरेशन करना है, तो आउटपुट क्रमशः 7, 9, 7, 6 होगा।
समाधान दृष्टिकोण
- एक मैप cnt (एलिमेंट → फ्रीक्वेंसी) परिभाषित करें
- एक मैप sts (फ्रीक्वेंसी → उस फ्रीक्वेंसी के एलिमेंट्स का स्टैक) परिभाषित करें
- maxFreq := 0
- append() में: cnt[x] बढ़ाएं, maxFreq अपडेट करें, x को sts[cnt[x]] में पुश करें
- pop() में: maxFreq से शीर्ष एलिमेंट पॉप करें, cnt घटाएं, यदि स्टैक खाली हो तो maxFreq घटाएं
उदाहरण कोड
#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;
}
};
int 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;
return 0;
}
इनपुट
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
व्याख्या
फ्रीक्वेंसी: 7→3, 9→2, 6→1। Pop क्रम: 7 (फ्रीक्वेंसी 3), 9 (फ्रीक्वेंसी 2, शीर्ष के निकटतम), 7 (फ्रीक्वेंसी 2), 6 (फ्रीक्वेंसी 1)।
निष्कर्ष
यह डिजाइन LeetCode "Maximum Frequency Stack" समस्या का समाधान है। सभी ऑपरेशन्स औसत O(1) समय में काम करते हैं। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।
