题目解析
题目要求实现一个LFU Cache,提供put、get两个操作。LFU就是 Least Frequently Used,也就是对每个key都会对它的操作进行计数count,但容器满了以后,把count最小的那个数删掉(如果最小的count有两个元素,那么按LRU来选择,即最早添加的删除)。
之所以它是hard,主要是因为它要求get和put的操作为O(1)。在LRU那道题里面使用一个list来保存所有的元素,使用unordered_map来保存key对应的list节点。现在需要保存key对应的count,以及根据count快速找到list节点。
方法
使用一个unordered_map<int, list<pair<int, int>>> count_to_keys
来保存count对应的元素,int low_count
保存当前最小count。这个最小的count主要用于删除节点使用。
关键函数是update(), 它会更新key对应的节点,具体逻辑看代码即可。
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
| class LFUCache { public: LFUCache(int capacity) { cap = capacity; size = 0; } int get(int key) { if (size == 0 || key_to_value.find(key) == key_to_value.end()) { return -1; } int value = key_to_value[key]->second; update(key, value); return value; } void put(int key, int value) { if (cap == 0) return; if (key_to_value.find(key) != key_to_value.end()) { update(key, value); return; } if (size == cap) delete_last(); insert_first(key, value); } private: void update(int key, int value) {
auto iter = key_to_value[key]; int count = key_to_count[key]; int new_count = count + 1; count_to_keys[count].erase(iter); if (low_count == count && count_to_keys[count].size() == 0) { low_count = new_count; } count_to_keys[new_count].push_front(make_pair(key, value)); auto new_iter = count_to_keys[new_count].begin(); key_to_value[key] = new_iter; key_to_count[key] = new_count; } void delete_last() {
auto iter = count_to_keys[low_count].end(); iter--; int key = iter->first; key_to_value.erase(key); key_to_count.erase(key); count_to_keys[low_count].erase(iter); size--; } void insert_first(int key, int value) {
size++; count_to_keys[0].push_front(make_pair(key, value)); auto iter = count_to_keys[0].begin(); key_to_value[key] = iter; key_to_count[key] = 0; if (low_count != 0) low_count = 0; } unordered_map<int, list<pair<int, int>>::iterator> key_to_value; unordered_map<int, list<pair<int, int>>> count_to_keys; unordered_map<int, int> key_to_count; int cap; int low_count = 0; int size; };
|