本題為11月30日力扣每日一題
題目來源:力扣第895題
題目tag:哈希表
題面
題目描述
設計一個類似堆疊的資料結構，將元素推入堆疊，并從堆疊中彈出出現頻率最高的元素，
實作 FreqStack 類:
- FreqStack() 構造一個空的堆疊，
- void push(int val) 將一個整數 val 壓入堆疊頂，
- int pop() 洗掉并回傳堆疊中出現頻率最高的元素，如果出現頻率最高的元素不只一個，則移除并回傳最接近堆疊頂的元素，
示例
輸入：
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
輸出：
[null,null,null,null,null,null,null,5,7,5,4]
解釋：
FreqStack = new FreqStack();
freqStack.push(5); //堆疊為 [5]
freqStack.push(7); //堆疊是 [5,7]
freqStack.push(5); //堆疊是 [5,7,5]
freqStack.push(7); //堆疊是 [5,7,5,7]
freqStack.push(4); //堆疊是 [5,7,5,7,4]
freqStack.push(5); //堆疊是 [5,7,5,7,4,5]
freqStack.pop(); //回傳 5 ，因為 5 出現頻率最高，堆疊變成 [5,7,5,7,4]，
freqStack.pop(); //回傳 7 ，因為 5 和 7 出現頻率最高，但7最接近頂部，堆疊變成 [5,7,5,4]，
freqStack.pop(); //回傳 5 ，因為 5 出現頻率最高，堆疊變成 [5,7,4]，
freqStack.pop(); //回傳 4 ，因為 4, 5 和 7 出現頻率最高，但 4 是最接近頂部的，堆疊變成 [5,7]，
提示
0 <= val <= $ 10^9 $
push 和 pop 的運算元不大于 $ 2 * 10^4 $，
輸入保證在呼叫 pop 之前堆疊中至少有一個元素，
思路分析
就我個人而言,當我看到題目要實作一個最大頻率堆疊的時候,我的第一反應是使用單調堆疊來解決(只是第一反應).而要維護這樣一個單調堆疊,就需要能在常數時間中取得當前元素的頻率
而每次在常數時間中取得當前元素的頻率這件事,顯然只需要將元素作為鍵,將出現頻率作為值,利用哈希表就可以完成了.想到這里我突然發現彈出最大頻率元素也可以用哈希表就可以直接解決了.
我們只需要維護一個哈希表,它以出現頻率為鍵,以這個頻率所有元素組成的堆疊為值(其實就是一組堆疊啦,只是借用了哈希表的邊長存盤和快速查找而已),在維護一個保存最大頻率的變數,就可以實作每次彈出最大頻率的元素啦!
或許這題的難點也在這里,資料的物理結構和邏輯結構并不需要完全對應,甚至可以完全不一樣.因為對外來說,內部的結構都是不可見的,所以只需要能完成指定的行為即可,無需拘泥于特定的形式.
參考代碼
class FreqStack
{
private:
// 最大頻率
int maxFreq;
// 記錄各個數頻率用的桶
unordered_map<int, int> book;
// 每個頻率對應的元素組成的各個堆疊的集合
unordered_map<int, stack<int>> bucket;
public:
/*
初始化物件
在C++中此處只需要初始化最大頻率屬性即可
*/
FreqStack()
{
maxFreq = 0;
}
/*
元素入堆疊
*/
void push(int val)
{
book[val]++; // 更新當前元素出現頻率
bucket[book[val]].push(val); // 將元素推入對應頻率的堆疊中
maxFreq = max(maxFreq, book[val]); // 更新最大頻率
}
int pop()
{
// 取出最大頻率對應的堆疊頂元素
int res = bucket[maxFreq].top();
bucket[maxFreq].pop();
// 料理后事
book[res]--;
if (bucket[maxFreq].empty()) // 如果空了,手動減小最大頻率
{
maxFreq--;
}
return res;
}
};
/**
* Your FreqStack object will be instantiated and called as such:
* FreqStack* obj = new FreqStack();
* obj->push(val);
* int param_2 = obj->pop();
*/
"正是我們每天反復做的事情，最終造就了我們，優秀不是一種行為，而是一種習慣" ---亞里士多德
這里是浙江理工大學22屆ACM集訓隊的成員一枚鴨!
本文首發于博客園，作者：星雙子，除了我自己的轉載請注明原文鏈接：https://www.cnblogs.com/geministar/p/LeetCode895.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/538833.html
標籤：其他