Giả sử chúng ta muốn tạo một ngăn xếp có tên là FrequencyStack, FrequencyStack của chúng tôi có hai chức năng -
-
append (x), Điều này sẽ nối thêm hoặc đẩy một giá trị x vào ngăn xếp.
-
pop (), Điều này sẽ loại bỏ và trả về phần tử thường xuyên nhất trong ngăn xếp. Nếu có nhiều hơn một phần tử có cùng tần số, thì phần tử gần đầu ngăn xếp nhất sẽ bị xóa và trả về.
Vì vậy, nếu đầu vào giống như nối một số phần tử như 7, 9, 7, 9, 6, 7, sau đó thực hiện các phép toán bật lên bốn lần, thì đầu ra sẽ tương ứng là 7,9,7,6.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một bản đồ cnt
-
Xác định một số bản đồ
-
maxFreq:=0
-
Xác định một hàm append (), điều này sẽ lấy x,
-
(tăng cnt [x] lên 1)
-
maxFreq:=tối đa của maxFreq và cnt [x]
-
chèn x vào sts [cnt [x]]
-
Xác định một hàm pop ()
-
maxKey:=maxFreq
-
x:=phần tử hàng đầu của sts [maxKey]
-
xóa phần tử khỏi sts [maxKey]
-
nếu kích thước của sts [maxKey] bằng 0, thì -
-
xóa maxKey khỏi sts
-
(giảm maxFreq xuống 1)
-
-
(giảm cnt [x] đi 1)
-
trả lại x
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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