146. LRU 缓存机制

[Geekhyt]

原题链接

借用 Map

Map 的键值是有序的，可以按照插入的顺序返回键值。

1. 元素存在就将其更新
2. this.cache.keys().next().value: 获取到头部元素(也就是最远使用的元素)的 key

const LRUCache = function(capacity) {
    this.cap = capacity
    this.cache = new Map()
}

LRUCache.prototype.get = function(key) {
    if (this.cache.has(key)) {
        let temp = this.cache.get(key)
        this.cache.delete(key)
        this.cache.set(key, temp)
        return temp
    } else {
        return -1
    }
}

LRUCache.prototype.put = function(key, value) {
    if (this.cache.has(key)) {
        this.cache.delete(key)
    } else if (this.cache.size === this.cap) {
        this.cache.delete(this.cache.keys().next().value)
    }
    this.cache.set(key,value)
}

• 时间复杂度：O(1)
• 空间复杂度：O(n)