460. LFU Cache

解題說明

C++ 解法

複雜度分析

虛擬碼

1. Maintain: keyMap (key -> node iterator), freqMap (freq -> node list), minFreq
2. get(key):
   a. If key not in keyMap, return -1
   b. Get node value, call touch(node) to increment frequency
   c. Return value
3. put(key, value):
   a. If capacity <= 0, return
   b. If key exists: update value, call touch(node), return
   c. If at capacity: remove last node from freqMap[minFreq], remove from keyMap
   d. Insert new node into freqMap[1] front, set minFreq = 1
4. touch(node):
   a. Remove node from freqMap[oldFreq]
   b. If freqMap[oldFreq] empty and minFreq == oldFreq: minFreq++
   c. Insert node into freqMap[oldFreq + 1] front

其他解法

延伸思考