成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[LeetCode] 460. LFU Cache

yacheng / 3282人閱讀

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?

Example

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 4
Solution 
class LFUCache {
    Map valMap;
    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);
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/77218.html

相關(guān)文章

  • LRU & LFU Cache

    摘要：首先要做到是，能想到的數(shù)據(jù)結(jié)構(gòu)只有兩三種，一個(gè)是，一個(gè)是，是，還有一個(gè)，是。不太可能，因?yàn)殚L(zhǎng)度要而且不可變，題目也沒說長(zhǎng)度固定?？梢宰龅胶投际?。因?yàn)檫€有函數(shù)，要可以，所以還需要一個(gè)數(shù)據(jù)結(jié)構(gòu)來記錄順序，自然想到。 LRU Cache 題目鏈接：https://leetcode.com/problems... 這個(gè)題要求O(1)的復(fù)雜度。首先要做到get(key)是O(1)，能想到的數(shù)據(jù)結(jié)...

    wenshi11019 評(píng)論0 收藏0

  • 論文《TinyLFU: A Highly Ecient Cache Admission Polic

    摘要：在靜態(tài)的頻率分布下，性能也落后于因?yàn)槠洳辉贋椴辉诰彺嬷械臄?shù)據(jù)維護(hù)任何頻率數(shù)據(jù)?？梢栽斠姷臏?zhǔn)入淘汰策略是新增一個(gè)新的元素時(shí)，判斷使用該元素替換一個(gè)舊元素，是否可以提升緩存命中率。 1. Introduction LFU的局限： LFU實(shí)現(xiàn)需要維護(hù)大而復(fù)雜的元數(shù)據(jù)（頻次統(tǒng)計(jì)數(shù)據(jù)等） 大多數(shù)實(shí)際工作負(fù)載中，訪問頻率隨著時(shí)間的推移而發(fā)生根本變化（這是外賣業(yè)務(wù)不適合樸素LFU的根本原因） 針...

    高璐 評(píng)論0 收藏0

  • 論文《TinyLFU: A Highly Ecient Cache Admission Polic

    摘要：在靜態(tài)的頻率分布下，性能也落后于因?yàn)槠洳辉贋椴辉诰彺嬷械臄?shù)據(jù)維護(hù)任何頻率數(shù)據(jù)。可以詳見的準(zhǔn)入淘汰策略是新增一個(gè)新的元素時(shí)，判斷使用該元素替換一個(gè)舊元素，是否可以提升緩存命中率。 1. Introduction LFU的局限： LFU實(shí)現(xiàn)需要維護(hù)大而復(fù)雜的元數(shù)據(jù)（頻次統(tǒng)計(jì)數(shù)據(jù)等） 大多數(shù)實(shí)際工作負(fù)載中，訪問頻率隨著時(shí)間的推移而發(fā)生根本變化（這是外賣業(yè)務(wù)不適合樸素LFU的根本原因） 針...

    RobinQu 評(píng)論0 收藏0

  • LFU

    摘要：如果每一個(gè)頻率放在一個(gè)里面，每個(gè)也有頭尾兩個(gè)指針，指向相鄰的。實(shí)際上相鄰的可以由的第一可以由的最后一個(gè)唯一確認(rèn)。也就是說，在的設(shè)計(jì)基礎(chǔ)上。也就是說頻率為的點(diǎn)，指向的下一個(gè)是頻率為的點(diǎn)移除和一樣。里存在的點(diǎn)，加到尾部的后一個(gè)。 只個(gè)代碼由LRU改進(jìn)得到。如果每一個(gè)頻率放在一個(gè)LRU里面，每個(gè)LRU也有頭尾兩個(gè)指針，指向相鄰的LRU。實(shí)際上相鄰的LRU可以由frequency = t+1的...

    whidy 評(píng)論0 收藏0

  • 筆記｜緩存

    摘要：緩存算法我是，我會(huì)統(tǒng)計(jì)每一個(gè)緩存數(shù)據(jù)的使用頻率，我會(huì)把使用最少的緩存替換出緩存區(qū)。瀏覽器就是使用了我作為緩存算法。在緩存系統(tǒng)中找出最少最近的對(duì)象是需要較高的時(shí)空成本。再來一次機(jī)會(huì)的緩存算法，是對(duì)的優(yōu)化。直到新的緩存對(duì)象被放入。 緩存 什么是緩存？ showImg(https://segmentfault.com/img/bVusZg); 存貯數(shù)據(jù)（使用頻繁的數(shù)據(jù)）的臨時(shí)地方，因?yàn)槿≡?..

    elliott_hu 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<