1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回 1
cache.put(3, 3);    // 去除 key 2
cache.get(2);       // 返回 -1 (未找到key 2)
cache.get(3);       // 返回 3
cache.put(4, 4);    // 去除 key 1
cache.get(1);       // 返回 -1 (未找到 key 1)
cache.get(3);       // 返回 3
cache.get(4);       // 返回 4

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

use std::{
    collections::{BTreeSet, HashMap},
    convert::TryInto,
};
#[derive(PartialEq, Eq, PartialOrd, Ord, Hash, Clone)]
struct CacheEntry {
    count: usize,
    used_time: usize,
    key: i32,
    value: i32,
}
/**
 * Your LFUCache object will be instantiated and called as such:
 * let obj = LFUCache::new(capacity);
 * let ret_1: i32 = obj.get(key);
 * obj.put(key, value);
 */
struct LFUCache {
    entry_map: HashMap<i32, CacheEntry>,  // key -> entry
    sorted_entries: BTreeSet<CacheEntry>, // sorted entries
    cap: usize,
    time: usize,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl LFUCache {
    fn new(capacity: i32) -> Self {
        Self {
            cap: capacity.try_into().unwrap(),
            time: 0,
            entry_map: HashMap::new(),
            sorted_entries: BTreeSet::new(),
        }
    }

    fn get(&mut self, key: i32) -> i32 {
        self.time += 1;
        match self.entry_map.get_mut(&key) {
            None => -1,
            Some(entry) => {
                self.sorted_entries.remove(entry);
                entry.count += 1;
                entry.used_time = self.time;
                self.sorted_entries.insert(entry.clone());

                entry.value
            }
        }
    }

    fn put(&mut self, key: i32, value: i32) {
        self.time += 1;
        if self.cap < 1 {
            return;
        }

        match self.entry_map.get_mut(&key) {
            Some(entry) => {
                self.sorted_entries.remove(entry);

                entry.count += 1;
                entry.used_time = self.time;
                entry.value = value;
                self.sorted_entries.insert(entry.clone());
            }
            None => {
                // 如果cache满了
                if self.is_full() {
                    // 删除最不常用的元素
                    let entry = self.sorted_entries.iter().next().unwrap().clone();
                    self.sorted_entries.remove(&entry);
                    self.entry_map.remove(&entry.key);
                }

                // 更新entry
                let entry = CacheEntry {
                    key,
                    value,
                    count: 1,
                    used_time: self.time,
                };
                self.entry_map.entry(key).or_insert(entry.clone());
                self.sorted_entries.insert(entry);
            }
        }
    }

    fn is_full(&self) -> bool {
        self.entry_map.len() >= self.cap
    }
}