- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
借用 Map
Map 的键值是有序的,可以按照插入的顺序返回键值。
- 元素存在就将其更新
this.cache.keys().next().value
: 获取到头部元素(也就是最远使用的元素)的 key
constLRUCache=function(capacity){this.cap=capacitythis.cache=newMap()}LRUCache.prototype.get=function(key){if(this.cache.has(key)){lettemp=this.cache.get(key)this.cache.delete(key)this.cache.set(key,temp)returntemp}else{return-1}}LRUCache.prototype.put=function(key,value){if(this.cache.has(key)){this.cache.delete(key)}elseif(this.cache.size===this.cap){this.cache.delete(this.cache.keys().next().value)}this.cache.set(key,value)}
- 时间复杂度:O(1)
- 空间复杂度:O(n)