要做list 還要記lter 懶== 用map會幫我排序 而且每次都加一 key才10個 heap上去再下來 應該也能平均O(1)吧><?? 人家list 70ms map 跑100ms 差不多了就這樣ㄅ 意思一樣啦>< class AllOne { public: unordered_map<string, int> keys; map<int, unordered_set<string>> buckets; AllOne() { } void inc(string key) { int ori = keys[key]; keys[key]++; buckets[ori].erase(key); if(buckets[ori].size() == 0) buckets.erase(ori); buckets[ori + 1].insert(key); } void dec(string key) { int ori = keys[key]; keys[key]--; buckets[ori].erase(key); if(buckets[ori].size() == 0) buckets.erase(ori); if(keys[key] == 0) keys.erase(key); else buckets[ori -1].insert(key); } string getMaxKey() { if(keys.empty()) return ""; auto it = buckets.end(); it--; auto& [i, s] = *it; return *s.begin(); } string getMinKey() { if(keys.empty()) return ""; auto it = buckets.begin(); auto& [i, s] = *it; return *s.begin(); } }; /** * Your AllOne object will be instantiated and called as such: * AllOne* obj = new AllOne(); * obj->inc(key); * obj->dec(key); * string param_3 = obj->getMaxKey(); * string param_4 = obj->getMinKey(); */ ※ 引述《JIWP (神楽めあ的錢包)》之銘言： : 432. All O`one Data Structure : 請實作一個資料結構 : 包含以下功能 : AllOne() : 初始化資料結構 : inc(string key) : 將key的次數+1，如果本來沒有key就將其插入 : dec(string key) : 將key的次數-1，如果次數變為0就把key移除 : getMaxKey() : 回傳最大次數的key，如果有多個則會傳任一個，若沒有任何key回傳-1 : getMinKey() : 回傳最小次數的key，如果有多個則回傳任一個，若沒有任何key回傳-1 : 以上操作都要在O(1)時間複雜度內 : 思路: : 用雙向鏈結串列，該鏈結串列的value是目前出現字串的次數 ----- Sent from JPTT on my iPad -- ※ 發信站: 批踢踢實業坊(ptt.org.tw), 來自: 123.205.121.194 (臺灣) ※ 文章網址: https://ptt.org.tw/Marginalman/M.1727633460.A.29D

推 CanIndulgeMe: 技術大神 09/30 02:15