460. LFU Cache

Hard

Description

設計一個 LFU (Least Frequently Used) 快取機制。實作 LFUCache 類別：get(key) 回傳 key 對應的值（不存在回傳 -1），put(key, value) 更新或插入。當容量滿時，移除使用頻率最低的 key；若頻率相同，移除最久未使用的。get 和 put 必須在 O(1) 時間內完成。

Example:

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]

Intuition#

核心思路：用三個 HashMap 分別管理 key->value、key->frequency、frequency->有序 key 集合，並追蹤最小頻率。

LFU 比 LRU 複雜，因為需要同時追蹤「使用頻率」和「同頻率下的使用順序」
需要快速找到最低頻率的最舊 key，並在頻率變化時更新
用 LinkedHashSet 維護每個頻率下的 key 順序（insertion order = LRU order）

Approaches#

1: Three HashMaps#

概念: keyToVal 存值、keyToFreq 存頻率、freqToKeys 用 LinkedHashSet 存同頻率的 key 順序，minFreq 追蹤最小頻率
時間複雜度: O(1) - get 和 put
空間複雜度: O(capacity)

class LFUCache(private val capacity: Int) {

    private val keyToVal = HashMap<Int, Int>()
    private val keyToFreq = HashMap<Int, Int>()
    private val freqToKeys = HashMap<Int, LinkedHashSet<Int>>()
    private var minFreq = 0

    fun get(key: Int): Int {
        if (key !in keyToVal) return -1
        increaseFreq(key)
        return keyToVal[key]!!
    }

    fun put(key: Int, value: Int) {
        if (capacity <= 0) return

        if (key in keyToVal) {
            keyToVal[key] = value
            increaseFreq(key)
            return
        }

        if (keyToVal.size >= capacity) {
            removeMinFreqKey()
        }

        keyToVal[key] = value
        keyToFreq[key] = 1
        freqToKeys.getOrPut(1) { LinkedHashSet() }.add(key)
        minFreq = 1
    }

    private fun increaseFreq(key: Int) {
        val freq = keyToFreq[key]!!
        keyToFreq[key] = freq + 1

        freqToKeys[freq]!!.remove(key)
        if (freqToKeys[freq]!!.isEmpty()) {
            freqToKeys.remove(freq)
            if (minFreq == freq) minFreq++
        }

        freqToKeys.getOrPut(freq + 1) { LinkedHashSet() }.add(key)
    }

    private fun removeMinFreqKey() {
        val keys = freqToKeys[minFreq]!!
        val evictKey = keys.iterator().next()
        keys.remove(evictKey)
        if (keys.isEmpty()) {
            freqToKeys.remove(minFreq)
        }
        keyToVal.remove(evictKey)
        keyToFreq.remove(evictKey)
    }
}

⭐2: HashMap + Doubly Linked List per Frequency#

概念: 每個頻率維護一個雙向鏈結串列，HashMap 直接映射到節點，所有操作 O(1)
時間複雜度: O(1) - get 和 put
空間複雜度: O(capacity)

class LFUCache(private val capacity: Int) {

    private class Node(val key: Int, var value: Int) {
        var freq = 1
        var prev: Node? = null
        var next: Node? = null
    }

    private class DoublyLinkedList {
        val head = Node(0, 0)
        val tail = Node(0, 0)
        var size = 0

        init {
            head.next = tail
            tail.prev = head
        }

        fun addFirst(node: Node) {
            node.next = head.next
            node.prev = head
            head.next!!.prev = node
            head.next = node
            size++
        }

        fun remove(node: Node) {
            node.prev!!.next = node.next
            node.next!!.prev = node.prev
            size--
        }

        fun removeLast(): Node {
            val node = tail.prev!!
            remove(node)
            return node
        }

        fun isEmpty(): Boolean = size == 0
    }

    private val keyToNode = HashMap<Int, Node>()
    private val freqToList = HashMap<Int, DoublyLinkedList>()
    private var minFreq = 0

    fun get(key: Int): Int {
        val node = keyToNode[key] ?: return -1
        increaseFreq(node)
        return node.value
    }

    fun put(key: Int, value: Int) {
        if (capacity <= 0) return

        val existing = keyToNode[key]
        if (existing != null) {
            existing.value = value
            increaseFreq(existing)
            return
        }

        if (keyToNode.size >= capacity) {
            val list = freqToList[minFreq]!!
            val removed = list.removeLast()
            keyToNode.remove(removed.key)
            if (list.isEmpty()) freqToList.remove(minFreq)
        }

        val node = Node(key, value)
        keyToNode[key] = node
        freqToList.getOrPut(1) { DoublyLinkedList() }.addFirst(node)
        minFreq = 1
    }

    private fun increaseFreq(node: Node) {
        val freq = node.freq
        val list = freqToList[freq]!!
        list.remove(node)
        if (list.isEmpty()) {
            freqToList.remove(freq)
            if (minFreq == freq) minFreq++
        }

        node.freq++
        freqToList.getOrPut(node.freq) { DoublyLinkedList() }.addFirst(node)
    }
}

minFreq 的更新邏輯是關鍵：increaseFreq 時如果舊頻率的 list 清空且等於 minFreq 就加 1；put 新 key 時 minFreq 直接設為 1。

🔑 Takeaways#

Pattern: LFU 是 LRU 的進階版，需要額外的頻率維度管理。三個 HashMap 方案更易理解，雙向鏈結串列方案更正統
關鍵技巧: LinkedHashSet 天然維護插入順序，可以用來在同頻率下模擬 LRU；minFreq 的正確更新是整道題的核心