Design - 460. LFU Cache
460. LFU Cache
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.
Note that the number of times an item is used is the number of calls to the get and put functions for that item since it was inserted. This number is set to zero when the item is removed.
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思路：
题目意思是要求实现一个数据结构，最小频率使用的高速缓存，LFU，是146题LRU的变形题，实现办法有很多，可以使用hashmap和bst来做，但是时间复杂度就是O(logK)，题目提议是做到常数的时间复杂度，O(1)，就只能用双向链表加上hashmap来做，因为双向链表移除一个元素的操作是O(1)的。
- 首先使用一个hashmap来存储key和节点对象。
- 而双向链表存储的是同一频率下的所有key，和lru类似，最近使用的放在链表头。
- 通过hashmap中的节点对象可以找到对应的双向循环链表中的位置，就可以移动key在频率链表中的位置，并且使用一个minFreq来记录最小频率的链表，这样在这个数据结构capacity满的时候，就能从最小频率的最久没使用过的位置删除数据节点。
代码:
go：
type LFUCache struct {
nodeMap map[int]*cacheNode // key-> api存入的value
listMap map[int]*doubleList // key-> freq
capacity int
minFreq int // 最小频率
}
type cacheNode struct {
key int
value int
freq int
keyNode *listNode
}
type listNode struct {
key int
next *listNode
prev *listNode
}
type doubleList struct {
head *listNode
tail *listNode
size int
}
func newList() *doubleList {
headNode := &listNode{}
tailNode := &listNode{}
headNode.next = tailNode
tailNode.prev = headNode
return &doubleList{head:headNode, tail:tailNode}
}
// 从双向循环链表中移除node节点
func (dl *doubleList) remove(node *listNode) {
node.prev.next = node.next
node.next.prev = node.prev
dl.size--
}
// 从双向循环链表中添加node节点到链表最前面
func (dl *doubleList) insert(node *listNode) {
dl.head.next.prev = node
node.next = dl.head.next
dl.head.next = node
node.prev = dl.head
dl.size++
}
// 移除最后一个元素，并取出
func (dl *doubleList) popback() *listNode {
listNode := dl.tail.prev
dl.remove(dl.tail.prev)
return listNode
}
func Constructor(capacity int) LFUCache {
return LFUCache {
nodeMap : make(map[int]*cacheNode),
listMap : make(map[int]*doubleList),
capacity : capacity,
}
}
func (this *LFUCache) Get(key int) int {
node, ok := this.nodeMap[key]
if !ok {
return -1
}
this.touch(node)
return node.value
}
func (this *LFUCache) touch(node *cacheNode) {
// 1. 更新频率
prevFreq := node.freq
node.freq++
freq := node.freq
// 2. 把节点在原来的频率list里面移除
dl := this.listMap[prevFreq]
dl.remove(node.keyNode)
if dl.size == 0 && prevFreq == this.minFreq {
// delete this list
delete(this.listMap, prevFreq)
this.minFreq++
}
// 3. 把节点插入到新的频率链表
dl, ok := this.listMap[freq]
if !ok {
dl = newList()
this.listMap[freq] = dl
}
dl.insert(node.keyNode)
}
func (this *LFUCache) Put(key int, value int) {
if this.capacity == 0 {
return
}
node, ok := this.nodeMap[key]
if ok {
// 更新value值
node.value = value
this.touch(node)
return
}
if len(this.nodeMap) == this.capacity {
// 没有容量需要删除最小频率的那个节点
// 删除最小频率节点
removeNode := (this.listMap[this.minFreq]).popback()
// 从nodeMap中移除
delete(this.nodeMap, removeNode.key)
}
// 添加新的节点
freq := 1
this.minFreq = freq
dl, ok := this.listMap[this.minFreq]
if !ok {
dl = newList()
this.listMap[this.minFreq] = dl
}
lNode := &listNode{key:key}
dl.insert(lNode)
this.nodeMap[key] = &cacheNode{
key : key,
value : value,
freq : freq,
keyNode : lNode,
}
}
/**
* Your LFUCache object will be instantiated and called as such:
* obj := Constructor(capacity);
* param_1 := obj.Get(key);
* obj.Put(key,value);
*/