460. LFU 缓存

🔴 🔖 设计 哈希表 链表 双向链表 🔗 力扣open in new window LeetCodeopen in new window

题目

Design and implement a data structure for a Least Frequently Used (LFU)open in new window cache.

Implement the LFUCache class:

LFUCache(int capacity) Initializes the object with the capacity of the data structure.
int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1.
void put(int key, int value) Update the value of the key if present, or inserts the key if not already present. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be invalidated.

To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.

When a key is first inserted into the cache, its use counter is set to 1 (due to the put operation). The use counter for a key in the cache is incremented either a get or put operation is called on it.

The functions get and put must each run in O(1) average time complexity.

Example 1:

Input

["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]

[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]

Output

[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

Explanation

// cnt(x) = the use counter for key x

// cache=[] will show the last used order for tiebreakers (leftmost element is most recent)

LFUCache lfu = new LFUCache(2);

lfu.put(1, 1); // cache=[1,_], cnt(1)=1

lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1

lfu.get(1); // return 1

// cache=[1,2], cnt(2)=1, cnt(1)=2

lfu.put(3, 3); // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2.

// cache=[3,1], cnt(3)=1, cnt(1)=2

lfu.get(2); // return -1 (not found)

lfu.get(3); // return 3

// cache=[3,1], cnt(3)=2, cnt(1)=2

lfu.put(4, 4); // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1.

// cache=[4,3], cnt(4)=1, cnt(3)=2

lfu.get(1); // return -1 (not found)

lfu.get(3); // return 3

// cache=[3,4], cnt(4)=1, cnt(3)=3

lfu.get(4); // return 4

// cache=[4,3], cnt(4)=2, cnt(3)=3

Constraints:

1 <= capacity <= 10^4
0 <= key <= 10^5
0 <= value <= 10^9
At most 2 * 10^5 calls will be made to get and put.

题目大意

请你为最不经常使用（LFU）open in new window缓存算法设计并实现数据结构。

实现 LFUCache 类：

LFUCache(int capacity): 用数据结构的容量 capacity 初始化对象
int get(int key): 如果键 key 存在于缓存中，则获取键的值，否则返回 -1 。
void put(int key, int value): 如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最久未使用 的键。

为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入：

["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]

[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]

输出：

[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

解释：

// cnt(x) = 键 x 的使用计数

// cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的）

LFUCache lfu = new LFUCache(2);

lfu.put(1, 1); // cache=[1,_], cnt(1)=1

lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1

lfu.get(1); // 返回 1

// cache=[1,2], cnt(2)=1, cnt(1)=2

lfu.put(3, 3); // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小

// cache=[3,1], cnt(3)=1, cnt(1)=2

lfu.get(2); // 返回 -1（未找到）

lfu.get(3); // 返回 3

// cache=[3,1], cnt(3)=2, cnt(1)=2

lfu.put(4, 4); // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用

// cache=[4,3], cnt(4)=1, cnt(3)=2

lfu.get(1); // 返回 -1（未找到）

lfu.get(3); // 返回 3

// cache=[3,4], cnt(4)=1, cnt(3)=3

lfu.get(4); // 返回 4

// cache=[3,4], cnt(4)=2, cnt(3)=3

提示：

1 <= capacity <= 10^4
0 <= key <= 10^5
0 <= value <= 10^9
最多调用 2 * 10^5 次 get 和 put 方法

解题思路

核心思路

双向链表 (Doubly Linked List):
- 每个频率下的键集合由一个双向链表管理，方便 O(1) 删除和插入操作。
数据结构：
- 哈希表 1: keyToNode，将键映射到链表节点。
- 哈希表 2: freqToList，将每个频率映射到一个双向链表。
- 记录当前最低频率 minFreq，便于快速定位删除键。

数据结构设计

LFUCache:
    keyToNode: { key: Node }       // 每个键对应的节点
    freqToList: { freq: DLinkedList }  // 每个频率对应的双向链表
    minFreq: 当前最低频率
    capacity: 缓存容量

Node:
    key: 键
    value: 值
    freq: 频率
    prev, next: 指向链表前后节点

DLinkedList:
    head, tail: 虚拟头尾节点
    size: 当前链表大小
    addNode(node): 添加节点
    removeNode(node): 删除节点
    removeLast(): 删除链表最后一个节点

代码思路

双向链表操作：
- addNode：在链表头部插入节点。
- removeNode：移除链表中的节点。
- removeLast：删除链表尾部节点（用于移除最少频率中最旧的键）。
get(key)：
- 检查 key 是否存在。
- 如果存在，更新节点频率并返回值。
put(key, value)：
- 如果键已存在，更新值并更新频率。
- 如果键不存在，检查容量是否已满：
  - 若满，则移除最低频率中最久未使用的键。
- 插入新节点到频率为 1 的链表。
updateNode(node)：
- 移除节点的旧频率。
- 更新节点频率并插入新的频率链表。
- 如果旧频率链表为空且该频率是最低频率，更新 minFreq。

复杂度分析

时间复杂度： O(1)，因为哈希表和双向链表的操作都是常数时间。
空间复杂度： O(n)，存储缓存数据和辅助数据结构。

代码

class LFUCache {
	constructor(capacity) {
		this.capacity = capacity; // 缓存容量
		this.size = 0; // 当前缓存大小
		this.minFreq = 0; // 当前最低频率
		this.keyToNode = new Map(); // 键到节点的映射
		this.freqToList = new Map(); // 频率到双向链表的映射
	}

	get(key) {
		if (!this.keyToNode.has(key)) return -1;

		const node = this.keyToNode.get(key);
		this.updateNode(node); // 更新节点频率
		return node.value;
	}

	put(key, value) {
		if (this.capacity === 0) return;

		if (this.keyToNode.has(key)) {
			const node = this.keyToNode.get(key);
			node.value = value; // 更新值
			this.updateNode(node); // 更新频率
		} else {
			if (this.size === this.capacity) {
				// 容量已满，移除最少频率的最久未使用节点
				const minFreqList = this.freqToList.get(this.minFreq);
				const toRemove = minFreqList.removeLast();
				this.keyToNode.delete(toRemove.key);
				this.size--;
			}

			// 插入新节点
			const newNode = new Node(key, value);
			this.keyToNode.set(key, newNode);
			if (!this.freqToList.has(1)) {
				this.freqToList.set(1, new DLinkedList());
			}
			this.freqToList.get(1).addNode(newNode);
			this.minFreq = 1; // 新插入节点的频率为 1
			this.size++;
		}
	}

	updateNode(node) {
		const freq = node.freq;
		const list = this.freqToList.get(freq);
		list.removeNode(node); // 从当前频率链表中移除

		if (list.size === 0 && freq === this.minFreq) {
			this.minFreq++; // 更新最低频率
		}

		node.freq++; // 增加频率
		if (!this.freqToList.has(node.freq)) {
			this.freqToList.set(node.freq, new DLinkedList());
		}
		this.freqToList.get(node.freq).addNode(node);
	}
}

class Node {
	constructor(key, value) {
		this.key = key;
		this.value = value;
		this.freq = 1;
		this.prev = null;
		this.next = null;
	}
}

class DLinkedList {
	constructor() {
		this.head = new Node(); // 虚拟头节点
		this.tail = new Node(); // 虚拟尾节点
		this.head.next = this.tail;
		this.tail.prev = this.head;
		this.size = 0;
	}

	addNode(node) {
		// 在头部添加节点
		node.next = this.head.next;
		node.prev = this.head;
		this.head.next.prev = node;
		this.head.next = node;
		this.size++;
	}

	removeNode(node) {
		// 删除节点
		node.prev.next = node.next;
		node.next.prev = node.prev;
		this.size--;
	}

	removeLast() {
		// 删除链表最后一个节点（真实节点）
		if (this.size === 0) return null;
		const last = this.tail.prev;
		this.removeNode(last);
		return last;
	}
}

题号	标题	题解	标签	难度	力扣
146	LRU 缓存	[✓]	`设计` `哈希表` `链表` `1+`	🟠	🀄️open in new window 🔗open in new window
588	设计内存文件系统 🔒		`设计` `字典树` `哈希表` `2+`	🔴	🀄️open in new window 🔗open in new window

460. LFU 缓存

# 460. LFU 缓存

# 题目

# 题目大意

# 解题思路

# 核心思路

# 数据结构设计

# 代码思路

# 复杂度分析

# 代码

# 相关题目

460. LFU 缓存

题目

题目大意

解题思路

核心思路

数据结构设计

代码思路

复杂度分析

代码

相关题目