Problem
Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.
Follow up:
Could you do both operations in O(1) time complexity?
LFUCache cache = new LFUCache( 2 / capacity / );
cache.put(1, 1); cache.put(2, 2); cache.get(1); // returns 1 cache.put(3, 3); // evicts key 2 cache.get(2); // returns -1 (not found) cache.get(3); // returns 3. cache.put(4, 4); // evicts key 1. cache.get(1); // returns -1 (not found) cache.get(3); // returns 3 cache.get(4); // returns 4Solution
class LFUCache { MapvalMap; Map freqMap; Map > kSetMap; int size; int min; public LFUCache(int capacity) { min = 0; size = capacity; valMap = new HashMap<>(); freqMap = new HashMap<>(); kSetMap = new HashMap<>(); kSetMap.put(1, new LinkedHashSet<>()); } public int get(int key) { if (!valMap.containsKey(key)) return -1; //get frequency, then update freqMap, kSetMap, min int frequency = freqMap.get(key); freqMap.put(key, frequency+1); kSetMap.get(frequency).remove(key); if (!kSetMap.containsKey(frequency+1)) { kSetMap.put(frequency+1, new LinkedHashSet<>()); } kSetMap.get(frequency+1).add(key); if (min == frequency && kSetMap.get(frequency).size() == 0) { min++; } return valMap.get(key); } public void put(int key, int value) { if (size <= 0) return; //when key is existed, just update valMap value, //and call get(key) to update freqmap, kSetMap and min if (valMap.containsKey(key)) { valMap.put(key, value); get(key); return; } //when reached capacity, remove min in all 3 maps if (valMap.size() == size) { int minKey = kSetMap.get(min).iterator().next(); valMap.remove(minKey); freqMap.remove(minKey); kSetMap.get(min).remove(minKey); } //add the fresh k-v pair to all 3 maps valMap.put(key, value); freqMap.put(key, 1); kSetMap.get(1).add(key); } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/77218.html
摘要:首先要做到是,能想到的數據結構只有兩三種,一個是,一個是,是,還有一個,是。不太可能,因為長度要而且不可變,題目也沒說長度固定。可以做到和都是。因為還有函數,要可以,所以還需要一個數據結構來記錄順序,自然想到。 LRU Cache 題目鏈接:https://leetcode.com/problems... 這個題要求O(1)的復雜度。首先要做到get(key)是O(1),能想到的數據結...
摘要:在靜態的頻率分布下,性能也落后于因為其不再為不在緩存中的數據維護任何頻率數據。可以詳見的準入淘汰策略是新增一個新的元素時,判斷使用該元素替換一個舊元素,是否可以提升緩存命中率。 1. Introduction LFU的局限: LFU實現需要維護大而復雜的元數據(頻次統計數據等) 大多數實際工作負載中,訪問頻率隨著時間的推移而發生根本變化(這是外賣業務不適合樸素LFU的根本原因) 針...
摘要:在靜態的頻率分布下,性能也落后于因為其不再為不在緩存中的數據維護任何頻率數據。可以詳見的準入淘汰策略是新增一個新的元素時,判斷使用該元素替換一個舊元素,是否可以提升緩存命中率。 1. Introduction LFU的局限: LFU實現需要維護大而復雜的元數據(頻次統計數據等) 大多數實際工作負載中,訪問頻率隨著時間的推移而發生根本變化(這是外賣業務不適合樸素LFU的根本原因) 針...
摘要:緩存算法我是,我會統計每一個緩存數據的使用頻率,我會把使用最少的緩存替換出緩存區。瀏覽器就是使用了我作為緩存算法。在緩存系統中找出最少最近的對象是需要較高的時空成本。再來一次機會的緩存算法,是對的優化。直到新的緩存對象被放入。 緩存 什么是緩存? showImg(https://segmentfault.com/img/bVusZg); 存貯數據(使用頻繁的數據)的臨時地方,因為取原始...
閱讀 2062·2023-04-25 21:11
閱讀 2963·2021-09-30 09:47
閱讀 2272·2021-09-24 09:48
閱讀 4428·2021-08-23 09:43
閱讀 895·2019-08-30 15:54
閱讀 559·2019-08-28 18:01
閱讀 1397·2019-08-27 10:55
閱讀 588·2019-08-27 10:55