05 堆 / 优先队列 / 系统设计

数据流处理，QR常见场景

🔖 #295 · Find Median from Data Stream ★

难度: Hard | 标签: Heap, Design | 链接: https://leetcode.com/problems/find-median-from-data-stream/

题目描述

设计数据结构，支持动态插入并在 O(log n) 时间内获取当前中位数。

解题思路

双堆：一个大顶堆（较小半部分）和一个小顶堆（较大半部分）。

答案代码


import heapq
class MedianFinder:
    def __init__(self):
        self.lo = []  # max heap (negate)
        self.hi = []  # min heap

    def addNum(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.lo) < len(self.hi):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def findMedian(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

扩展总结

QR 数据流场景：算法交易 PnL 实时中位数等

变体：#480 Sliding Window Median（加上满足大小的堆删除）

🔖 #23 · Merge k Sorted Lists ★

难度: Hard | 标签: Heap, Linked List | 链接: https://leetcode.com/problems/merge-k-sorted-lists/

题目描述

合并 k 个有序链表。

解题思路

用优先队列（最小堆）维护各链表当前节点，每次弹出最小并把其下一节点入堆。

答案代码


import heapq
def mergeKLists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    dummy = cur = ListNode(0)
    while heap:
        val, i, node = heapq.heappop(heap)
        cur.next = node
        cur = cur.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

扩展总结

也可用分治 (Divide & Conquer) O(n log k)

(val, i, node) 中 i 用于打破值相同时的平局问题

🔖 #146 · LRU Cache ★

难度: Medium | 标签: Design, HashMap, Linked List | 链接: https://leetcode.com/problems/lru-cache/

题目描述

设计一个满足 LRU 缓存约束的数据结构。

解题思路

HashMap + 双向链表：链表维护访问顺序，HashMap O(1) 定位。

答案代码


from collections import OrderedDict
class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = OrderedDict()
    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]
    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)

扩展总结

Python 的 OrderedDict 就是底层实现，面试要知道原理

#460 LFU Cache 是 LRU 的进阶，需要按频次排序

🔖 #347 · Top K Frequent Elements ★

难度: Medium | 标签: Heap, Bucket Sort | 链接: https://leetcode.com/problems/top-k-frequent-elements/

题目描述

找出现频次最高的 k 个元素。

解题思路

堆：O(n log k)，维护大小为 k 的小顶堆

桶排序：O(n)，按频次分桶

答案代码


from collections import Counter
def topKFrequent(nums, k):
    count = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        buckets[freq].append(num)
    res = []
    for i in range(len(buckets)-1, 0, -1):
        res.extend(buckets[i])
        if len(res) >= k:
            return res[:k]

扩展总结

桶排序是 O(n) 最优解法，但堆方案更通用

快选 (QuickSelect) 也可到达O(n)平均