146. LRU 缓存
2022-07-25 本文已影响0人
邦_
因为函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
那只有哈希表能做到了。。
自己想的= =。。用数组存个key。耗时1752 = =。。无语了
因为数组的查找遍历、删除、插入 都是o(n)级别的= =
需要自己实现一个双向链表来优化这个复杂度
class LRUCache {
var array = Array<Int>()
var map = Dictionary<Int,Int>()
var maxLen = 0
init(_ capacity: Int) {
maxLen = capacity
}
func get(_ key: Int) -> Int {
if let num = map[key] {
for (index,tempKey) in array.enumerated() {
if key == tempKey {
array.remove(at: index)
array.insert(key, at: 0)
break
}
}
return num
}
return -1
}
func put(_ key: Int, _ value: Int) {
let len = array.count
//如果存在的话
if let _ = map[key] {
for (index,tempKey) in array.enumerated() {
if key == tempKey {
array.remove(at: index)
array.insert(key, at: 0)
break
}
}
}
//不存在
else{
//达到最大容量了
if len == maxLen {
map.removeValue(forKey: array.removeLast())
array.insert(key, at: 0)
}else {
array.insert(key, at: 0)
}
}
map[key] = value
// print(array)
}
}
双向链表= =。。还是1000多ms
public class LRUNode {
public var val: Int
public var key: Int
public var next: LRUNode?
public var prev: LRUNode?
public init() { self.val = 0; self.key = 0;self.next = nil; self.prev = nil; }
public init(_ key:Int,_ val: Int) { self.val = val;self.key = key; self.next = nil; self.prev = nil; }
}
class LRUCache {
var map = Dictionary<Int,LRUNode>()
var maxLen = 0
var len = 0
var first = LRUNode()
var last = LRUNode()
init(_ capacity: Int) {
maxLen = capacity
first.next = last
last.prev = first
}
func get(_ key: Int) -> Int {
if let tempNode = map[key] {
// 删除tempNode
removeNode(tempNode)
//然后放到前边
afterFirstNode(tempNode)
// print(tempNode.val)
return tempNode.val
}
return -1
}
func put(_ key: Int, _ value: Int) {
//如果存在的话
if let tempNode = map[key] {
tempNode.val = value
map[key] = tempNode
// 删除tempNode
removeNode(tempNode)
//然后放到前边
afterFirstNode(tempNode)
}
//不存在
else{
//达到最大容量了
if len == maxLen {
// 删除最后一个节点
// print(last.prev!.val)
let lastNode = last.prev!
removeNode(lastNode)
map.removeValue(forKey: lastNode.key)
let tempNode = LRUNode(key,value)
map[key] = tempNode
afterFirstNode(tempNode)
}else {
let tempNode = LRUNode(key,value)
map[key] = tempNode
len += 1
afterFirstNode(tempNode)
}
}
}
func removeNode(_ tempNode:LRUNode){
//前一个节点
let prevNode = tempNode.prev
//后一个节点
let lastNode = tempNode.next
prevNode?.next = lastNode
lastNode?.prev = prevNode
}
func afterFirstNode(_ tempNode:LRUNode){
let afterNode = first.next!
tempNode.prev = first
first.next = tempNode
tempNode.next = afterNode
afterNode.prev = tempNode
}
}
继续优化下= =。。
public class LRUNode {
public var val: Int
public var key: Int
public var next: LRUNode?
public var prev: LRUNode?
public init() { self.val = 0; self.key = 0;self.next = nil; self.prev = nil; }
public init(_ key:Int,_ val: Int) { self.val = val;self.key = key; self.next = nil; self.prev = nil; }
}
class LRUCache {
var map = Dictionary<Int,LRUNode>()
var maxLen = 0
var len = 0
var first = LRUNode()
var last = LRUNode()
init(_ capacity: Int) {
maxLen = capacity
first.next = last
last.prev = first
}
func get(_ key: Int) -> Int {
if let tempNode = map[key] {
// 删除tempNode
removeNode(tempNode)
//然后放到前边
afterFirstNode(tempNode)
// print(tempNode.val)
return tempNode.val
}
return -1
}
func put(_ key: Int, _ value: Int) {
//如果存在的话
if let tempNode = map[key] {
tempNode.val = value
// 删除tempNode
removeNode(tempNode)
//然后放到前边
afterFirstNode(tempNode)
}
//不存在
else{
//达到最大容量了
if len == maxLen {
// 删除最后一个节点
// print(last.prev!.val)
let lastNode = last.prev!
removeNode(lastNode)
map.removeValue(forKey: lastNode.key)
let tempNode = LRUNode(key,value)
map[key] = tempNode
afterFirstNode(tempNode)
}else {
let tempNode = LRUNode(key,value)
map[key] = tempNode
len += 1
afterFirstNode(tempNode)
}
}
}
func removeNode(_ tempNode:LRUNode){
tempNode.prev?.next = tempNode.next
tempNode.next?.prev = tempNode.prev
}
func afterFirstNode(_ tempNode:LRUNode){
let afterNode = first.next!
tempNode.prev = first
first.next = tempNode
tempNode.next = afterNode
afterNode.prev = tempNode
}
}
