LeetCode 460. LFU 缓存

Categories:

Tags:

题目描述
思路分析
1. 解法一：哈希表 + 频次链表（推荐）
相似题目

题目描述

✅ 460. LFU 缓存

思路分析

解法一：哈希表 + 频次链表（推荐）

核心思路：

哈希表保存 key -> Node，Node 记录 key/value/freq。

另一个哈希表保存 freq -> 双向链表，链表内按访问顺序维护 LRU。

访问或更新时提升频次：从旧频次链表移除，加入新频次链表。

需要淘汰时，从 minFreq 对应链表尾部删除。

复杂度分析：

时间复杂度：O(1)，每次操作均为常数时间。

空间复杂度：O(capacity)，用于节点与频次链表。

import java.util.*;

class LFUCache {
    private static class Node {
        int key;
        int value;
        int freq;
        Node prev;
        Node next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.freq = 1;
        }
    }

    private static class DLinkedList {
        Node head;
        Node tail;
        int size;

        DLinkedList() {
            head = new Node(0, 0);
            tail = new Node(0, 0);
            head.next = tail;
            tail.prev = head;
        }

        void addFirst(Node node) {
            node.next = head.next;
            node.prev = head;
            head.next.prev = node;
            head.next = node;
            size++;
        }

        void remove(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            size--;
        }

        Node removeLast() {
            if (size == 0) {
                return null;
            }
            Node node = tail.prev;
            remove(node);
            return node;
        }
    }

    private final int capacity;
    private int minFreq;
    private final Map<Integer, Node> nodeMap;
    private final Map<Integer, DLinkedList> freqMap;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minFreq = 0;
        this.nodeMap = new HashMap<>();
        this.freqMap = new HashMap<>();
    }

    public int get(int key) {
        Node node = nodeMap.get(key);
        if (node == null) {
            return -1;
        }
        increaseFreq(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }

        Node node = nodeMap.get(key);
        if (node != null) {
            node.value = value;
            increaseFreq(node);
            return;
        }

        if (nodeMap.size() == capacity) {
            DLinkedList minList = freqMap.get(minFreq);
            Node removed = minList.removeLast();
            nodeMap.remove(removed.key);
        }

        Node newNode = new Node(key, value);
        nodeMap.put(key, newNode);
        freqMap.computeIfAbsent(1, f -> new DLinkedList()).addFirst(newNode);
        minFreq = 1;
    }

    private void increaseFreq(Node node) {
        int freq = node.freq;
        DLinkedList list = freqMap.get(freq);
        list.remove(node);

        if (freq == minFreq && list.size == 0) {
            minFreq++;
        }

        node.freq++;
        freqMap.computeIfAbsent(node.freq, f -> new DLinkedList()).addFirst(node);
    }
}

type Node struct {
	key   int
	value int
	freq  int
	prev  *Node
	next  *Node
}

type DLinkedList struct {
	head *Node
	tail *Node
	size int
}

func newList() *DLinkedList {
	head := &Node{}
	tail := &Node{}
	head.next = tail
	tail.prev = head
	return &DLinkedList{head: head, tail: tail}
}

func (l *DLinkedList) addFirst(node *Node) {
	node.next = l.head.next
	node.prev = l.head
	l.head.next.prev = node
	l.head.next = node
	l.size++
}

func (l *DLinkedList) remove(node *Node) {
	node.prev.next = node.next
	node.next.prev = node.prev
	l.size--
}

func (l *DLinkedList) removeLast() *Node {
	if l.size == 0 {
		return nil
	}
	node := l.tail.prev
	l.remove(node)
	return node
}

type LFUCache struct {
	capacity int
	minFreq  int
	items    map[int]*Node
	freqs    map[int]*DLinkedList
}

func Constructor(capacity int) LFUCache {
	return LFUCache{
		capacity: capacity,
		minFreq:  0,
		items:    make(map[int]*Node),
		freqs:    make(map[int]*DLinkedList),
	}
}

func (c *LFUCache) Get(key int) int {
	node, ok := c.items[key]
	if !ok {
		return -1
	}
	c.increase(node)
	return node.value
}

func (c *LFUCache) Put(key int, value int) {
	if c.capacity == 0 {
		return
	}

	if node, ok := c.items[key]; ok {
		node.value = value
		c.increase(node)
		return
	}

	if len(c.items) == c.capacity {
		list := c.freqs[c.minFreq]
		removed := list.removeLast()
		delete(c.items, removed.key)
	}

	node := &Node{key: key, value: value, freq: 1}
	c.items[key] = node
	if _, ok := c.freqs[1]; !ok {
		c.freqs[1] = newList()
	}
	c.freqs[1].addFirst(node)
	c.minFreq = 1
}

func (c *LFUCache) increase(node *Node) {
	freq := node.freq
	list := c.freqs[freq]
	list.remove(node)
	if freq == c.minFreq && list.size == 0 {
		c.minFreq++
	}

	node.freq++
	if _, ok := c.freqs[node.freq]; !ok {
		c.freqs[node.freq] = newList()
	}
	c.freqs[node.freq].addFirst(node)
}

相似题目

题目	难度	考察点
146. LRU 缓存	中等	设计数据结构
432. 全 O(1) 的数据结构	困难	设计
355. 设计推特	中等	设计
380. O(1) 时间插入、删除和获取随机元素	中等	设计
716. 最大栈	困难	设计

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/80423869