Giả sử ta muốn xây dựng một stack gọi là FrequencyStack, có hai hàm:
- append(x): đẩy giá trị x vào stack.
- pop(): xóa và trả về phần tử xuất hiện nhiều nhất trong stack. Nếu có nhiều phần tử cùng tần suất cao nhất, xóa và trả về phần tử gần đỉnh nhất.
Ví dụ: append 7, 9, 7, 9, 6, 7, rồi pop 4 lần, đầu ra lần lượt: 7, 9, 7, 6.
Để giải quyết, ta làm theo các bước:
- Định nghĩa map cnt.
- Định nghĩa map sts.
- maxFreq := 0.
- Định nghĩa append(x): tăng cnt[x]; maxFreq = max(maxFreq, cnt[x]); chèn x vào sts[cnt[x]].
- Định nghĩa pop(): maxKey = maxFreq; x = đỉnh sts[maxKey]; xóa khỏi sts[maxKey]; nếu sts[maxKey] rỗng: xóa maxKey khỏi sts, giảm maxFreq; giảm cnt[x]; trả x.
Xem triển khai dưới đây:
Ví dụ
#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; }
Đầu vào
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;
Đầu ra
7 9 7 6