堆、哈希表与图

一节课塞进三种数据结构,它们共享同一个内核:每种结构只让你「一个操作」变便宜,而面试题的本质,就是认出这道题想要的是哪个便宜操作。Heap 用 O(1) 把最小值或最大值端到你面前,是所有 Top-K 题的引擎;HashMap 用 O(1) 给你成员判定和查找——前提是你懂这份承诺背后的隐藏条款;Graph 不过是节点、边,加上一个存储选择。这节课把三种结构从底层搭起来,再用同一小撮题——第 K 大、Top-K 词、缺失数字、数组交集——从排序、堆、哈希、双指针几个角度反复攻打,让你学会挑工具,而不是背一个。

堆、哈希表和图落在哪里

到这节课,工具箱已经很满了。Array 给了排序、binary search、two pointers;LinkedList 给了 dummy head、快慢指针、递归;Queue 和 Stack 给了有序访问;Tree 与 BST 给了两种递归思维——bottom-up(经典递归,结果顺着调用栈往上返)和 top-down(状态当参数往下带)——外加那招分治:用 O(n) 把一个 n 的问题拆成两个 n/2 的子问题,合并 O(n),整体 O(n log n)。

这节课补上三种在真实系统里天天出现的重量级结构:heap(Java 里以 PriorityQueue 暴露)、HashMap / HashTable / HashSet 家族,以及 graph。它们看着毫不相干,但贯穿线是同一条:认出这种结构把哪个操作变便宜,让它去驱动算法。

Heap = 完全二叉树,住在数组里

堆是一棵完全二叉树——除了最后一层可能没填满(且从左往右填),每层都是满的——外加一条排序规则:父亲比两个孩子都小(min-heap)或都大(max-heap)。关键在于,这只是父子间的规则。兄弟之间无序,不存在全序。这恰恰解释了为什么你只能信任最顶上那个元素。

因为树是完全的,它能无缝映射到一个没有空洞的数组。节点在下标 i(从 0 开始)时,父亲在 (i-1)/2,左孩子在 2i+1,右孩子在 2i+2。没有节点指针,内存连续,cache 友好。值得背下的五条:

• 堆序——min-heap(最小在顶)或 max-heap(最大在顶)。
• 永远是完全二叉树——正是这条不变式让数组表示成立。
• 只能访问 top——peek() 是你唯一能直接读的元素。
• 操作——insert(push/offer/add)、删顶(poll/remove)、读顶(peek/get)、update。
• 用 heapify 初始化——线性时间把任意数组变成合法堆。

在 Java 里,new PriorityQueue<>() 默认是 min-heap;传一个 Comparator 就能翻成 max-heap,或给自定义对象排序(下面细讲)。

亲手建一个堆——heapify、insert、delete

自己写一遍堆,哪怕只写一次,复杂度就全清楚了。这是一个建在原始 int[] 上的完整 min-heap:

public class Heap {
    public int[] A;          // 当作堆用的数组
    public int n;            // 活跃节点数

    public Heap(int[] B) {
        A = new int[B.length];
        System.arraycopy(B, 0, A, 0, B.length);
        n = A.length;
        for (int i = n / 2 - 1; i >= 0; i--)  // 只处理非叶节点,自底向上
            heapify(i);
    }

    private void heapify(int i) {                 // 把节点 i 下沉(min-heap)
        int left = 2 * i + 1, right = 2 * i + 2, min = i;
        if (left  < n && A[left]  < A[min]) min = left;   // 孩子必须存在(下标 < n)
        if (right < n && A[right] < A[min]) min = right;
        if (min != i) {
            int tmp = A[i]; A[i] = A[min]; A[min] = tmp;
            heapify(min);                          // 在交换落点继续下沉
        }
    }

    public void insert(int key) {                 // 追加到末尾,再上浮
        int i = n++;                              // 扩容;i 是新的末尾槽
        while (i > 0 && A[(i - 1) / 2] > key) {   // A[(i-1)/2] 是父亲
            A[i] = A[(i - 1) / 2];               // 父亲下滑
            i = (i - 1) / 2;
        }
        A[i] = key;
    }

    public int deleteRoot() {                    // 删掉最小值
        if (n < 1) return -1;                    // 空堆兜底
        int min = A[0];
        A[0] = A[--n];                          // 末尾元素当新根
        heapify(0);                             // 把它下沉回去
        return min;
    }
}

为什么 heapify 是 O(n) 而不是 O(n log n)。 诀窍在于叶子——下标 n/2 … n-1——本身就是合法的单元素堆,所以你根本不碰它们。你只下沉内部节点,从 n/2 - 1 一路到根。再按高度算工作量:高度 h 上至多 n / 2^(h+1) 个节点,每个下沉花 O(h)。总和是 Σ h · n / 2^(h+1),而这个级数收敛——Σ h / 2^h = 2——于是塌缩成 O(n)。建堆是线性的。(堆排序不是,因为随后 k 次 poll 每次都要 O(log n)。)insert 和删根各走一条根到叶的路径,所以都是 O(log n)。

第 K 大元素(LC 215)——四挡

LC 215 Kth Largest Element in an Array 是堆的招牌题,值得写四种解法,因为最优解取决于输入。

S1 — 排序后取下标。 降序排,返回 arr[k-1]。时间 O(n log n),一行就能写。先把它作为 baseline 报出来,再优化。

S2 — quickselect。 借用 quicksort 的 partition,但只递归进包含答案的那一侧。这里不需要全局有序;一旦 pivot 落到「前面恰好有 k-1 个更大元素」的位置,pivot 就是答案。partition 告诉你留哪边、扔哪边。

class Solution {
    private Random rand = new Random();

    public int findKthLargest(int[] nums, int k) {
        int index = quickSelect(nums, 0, nums.length - 1, k);
        return nums[index];
    }

    // 返回存放第 k 大值的下标
    private int quickSelect(int[] nums, int left, int right, int k) {
        int pivotIndex = left + rand.nextInt(right - left + 1);
        int pivot = nums[pivotIndex];
        swap(nums, pivotIndex, right);        // 先把 pivot 停到末尾

        int i = left, j = right - 1;
        while (i <= j) {
            while (i <= j && nums[i] < pivot) i++;   // 较小的漂到左边
            while (j >= i && nums[j] > pivot) j--;   // 较大的漂到右边
            if (i <= j) swap(nums, i++, j--);
        }
        swap(nums, i, right);                  // pivot 归位到最终槽

        int m = right - i + 1;                 // >= pivot 的元素个数
        if (m == k) return i;
        else if (m < k) return quickSelect(nums, left, i - 1, k - m);
        else return quickSelect(nums, i + 1, right, k);
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
    }
}

复杂度是整道题的重点。平均情况下,你花 O(n) 把 n 的问题缩到 n/2,于是 n + n/2 + n/4 + … = 2n → O(n)。最坏情况下,恶意 pivot 每趟只剥掉一个元素——n + (n-1) + (n-2) + … → O(n²)——这正是要随机化 pivot 的原因。空间 O(1),但注意它会改动原数组。排除左边时留意 offset:递归传的是 k - m,不是 k。

S3 — 完整的 size-n min-heap。 用 O(n) 把整个数组 heapify(或逐个 insert,O(n log n)),再 poll k 次,每次 O(log n)。合计 O(n + k log n),空间 O(n)。

S4 — 容量为 k 的有界 min-heap。 更漂亮的那个:维护一个永远不超过 k 个元素的 min-heap——目前见过的 k 个最大值。先把前 k 个 heapify(O(k)),之后每来一个元素,若比堆顶大,就弹掉堆顶再插入。size-k min-heap 的堆顶,从构造上讲就是第 k 大。

// 第 k 大 = k 个最大值里最小的那个 → 维护一个 size-k MIN-heap
public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();   // 默认 min-heap
    for (int val : nums) {
        pq.offer(val);
        if (pq.size() > k) pq.poll();      // 弹掉最小的,只留前 k 大
    }
    return pq.peek();                        // 堆顶 = 第 k 大
}

时间 O(k + (n-k) log k) ≈ O(n log k),空间 O(k)。S3 与 S4 之争取决于 k 相对 n 的大小。 当 k 很小(比如 k=1,「求最大值」),size-k 堆基本就是 O(n);当 k ≈ n/2 且数组能进内存时,quickselect 的 O(n) 完胜;当 k = n 时,不如直接排序。还有一个决定性的加分项:size-k 堆是唯一能在数据流式、装不进内存时存活的解——你一次只握 k 个元素。Follow-up 常问:「把前 k 小全部按 order 返回。」那就把这 k 个排序,或用 quickselect 圈出这一段再排。

Top K Frequent Words(LC 692)与 Comparator vs Comparable

一本书里的 Top K Frequent Words(LC 692) 把 HashMap 和堆串了起来。先把每个词的频率数进一个 Map<String, Integer>,把每个 (word, freq) 包成一个小对象,按频率推进一个 size-k 堆。要留下频率最高的 k 个,就用按频率的 min-heap,这样堆溢出时被挤出去的永远是频率最低的词。

comparator 的方向是整道题的关键,也是经典的翻车点。这里正好牵出 Comparable vs Comparator:

class Element {
    String word;
    int freq;
}

// return a.freq - b.freq  →  MIN-heap(频率最低在顶,会被弹出)
// return b.freq - a.freq  →  MAX-heap
PriorityQueue<Element> heap =
    new PriorityQueue<>((a, b) -> a.freq - b.freq);

// Comparable:类型唯一的自然序 —— 一个类只有一个
class Employee implements Comparable<Employee> {
    int salary;
    public int compareTo(Employee o) { return this.salary - o.salary; }  // 低薪在前
}

// Comparator:外部可插拔 —— 想定几个排序就定几个
Arrays.sort(employees, new Comparator<Employee>() {
    public int compare(Employee a, Employee b) { return a.getName().compareTo(b.getName()); }
});

Comparable 定义一个类型唯一的「自然」序,写在类自身的 compareTo 里——只能有一个。Comparator 是带 compare 方法的外部对象;你想定几个就定几个,甚至能给一个你改不了的类排序。正因为这份灵活,Comparator 是更推荐的默认。遍历 map 的 key 用 for (String key : map.keySet())。

笔记还列了三种把这道题放大的方式,顺带搭起系统设计的桥。S2 — TreeMap:红黑树保持 key 有序,想要有序遍历而不只是取 top k 时好用。S3 — 分布式 / 有限内存:书大到单机放不下时,把词分片到多台机器,每台算局部 top-k,再 merge。S4 — 大数据 / MapReduce:map 发射 (word, 1),reduce 对每个词求和,最后一趟 top-K 把各分片合并。你刚写的 size-k 堆,正是分片内和最终合并用的原语。

HashMap、HashTable 与 HashSet

区别先从「存什么」开始:Map 存 key→value 对;Set 只存 key,存在的意义是回答「我见过它吗?」。Set 是 interface,由 HashSet 实现,永不含重复;Map 是 interface,由 HashMap 实现。

非同步对象通常比同步对象性能好,所以 HashMap 是日常首选;真需要线程安全时再上专门的并发工具(或 ConcurrentHashMap)。核心 API 平均都是 O(1):

• Set——set.add(key)、set.contains(key)、set.remove(key)。add 返回 boolean:元素已存在时返回 false,这正是去重和求交集的诀窍。
• Map——map.put(key, value)、map.get(key)、map.containsKey(key)、map.remove(key)。put 返回旧值(或 null)——检测覆盖时很有用。

笔记里两条实战提醒。其一,往 HashSet 里塞对象做去重时,要想清楚你是按 reference 还是按 value 去重——后者需要正确实现 equals/hashCode,搞错了就是一个不报错的静默 bug。其二,若需要一对多映射,把多个字段打包成一个小类,拿它当 value。一个漂亮的现实例子是「阅后即焚」:Map<Key, (message, expire time)>——value 同时带着内容和一个 TTL,读取时检查是否过期。

HashMap 内部——get() 为什么 O(1)

面试官爱从「它是 O(1)」追问到「为什么」。答案是一串设计决策。

那份承诺。 hash function 把任意 key 变成一个 bucket 下标,这个下标稳定(同一 key 永远映到同一 bucket)、确定、且在 [0, capacity) 上无明显规律地均匀散开。正是它让查找是一次数组访问,而不是一次扫描。

碰撞不可避免。 由鸽笼原理,不同 key 迟早会落进同一 bucket。两种标准解法:separate chaining(每个 bucket 挂一条链表——链一长就转成树)和 open addressing(碰撞时向后探测到下一个空槽,如 linear probing)。

把 bucket 维持得短。 表越满碰撞越多,于是用 load factor 卡占用率。Java 在 0.75 时扩容:一旦表填到四分之三,就扩容并把每个条目 rehash 进更大的数组——新容量 ≈ n / 0.75,让表大致保持四分之一为空。扩容是 O(n),但很少发生,所以查找保持 摊还 O(1);病态的最坏情况是所有 key 撞进一个 bucket,退化到 O(n)。在分布式 hash table 里,同一思想以 consistent hashing 出现,它让增删 bucket 时需要搬动的 key 尽量少。

一个具体的字符串 hash function——多项式滚动哈希——能把它讲实:

int hash(String key) {
    int sum = 0;
    for (char c : key.toCharArray()) {
        sum = sum * 32 + (int) c;      // 多项式滚动哈希(31/32 是常见乘子)
        sum %= HASH_MAP_CAPACITY;         // 折回 bucket 取值范围
    }
    return sum;                           // 稳定、确定、均匀散开
}

乘一个小常数、再把每个字符折进去,能把相近的字符串(比如 "abc" 和 "acb")散到不同 bucket——正是这种散布让链保持短、让 get() 实质上是常数时间。

缺失数字(LC 268)——五个角度

LC 268 Missing Number——数组里有 n 个互不相同的数,取自 [0, n],恰好缺一个。五种解法,各教一个不同的条件反射:

• S1 — XOR。 把 0…n 每个下标和数组里每个值全部 XOR 起来。每个出现过的数都跟它的下标抵消(x ^ x = 0),只剩缺失的那个。O(n) 时间、O(1) 空间,还没有溢出风险——最干净的解。
• S2 — 求和。 期望和是 n(n+1)/2,减去数组实际和,差就是缺失数。O(n)/O(1),但 n 大时留意整型溢出。
• S3 — 排序后扫描。 排序,找第一个 value != index 的下标,或比较相邻元素。留意笔记点名的边界:只有一个元素,或缺的正好在最末尾。
• S4 — 排序 + binary search。 在有序的 [0…n]-缺一个上,nums[mid] > mid 说明缺口在左,否则在右。整体 O(n log n) 被排序主导,但很好地示范了缺失元素就是一个翻转边界——见 第 1 课。
• S5 — HashSet / HashMap。 把每个值丢进 set,再探测 0…n 找缺席者。它能干净地推广到更丰富的计数变体——「每个数出现 m 次,只有 n 个出现 k 次」——用频率 map 直接回答。

两个数组的交集(LC 349 / 350)

给两个数组,求公共元素。三种解法,按输入形状来选。

S1 — HashSet。 把较小的数组加进一个 set(省空间),再扫描较大的;凡是已在 set 里的元素就是公共元素。

public List<Integer> intersection(int[] arr1, int[] arr2) {
    if (arr1 == null || arr1.length == 0 ||
        arr2 == null || arr2.length == 0) return new ArrayList<>();

    if (arr1.length < arr2.length) return intersection(arr2, arr1);  // 让 set 装较小的那个

    List<Integer> ans = new ArrayList<>();
    Set<Integer> set = new HashSet<>();
    for (int x : arr2) set.add(x);        // 较小数组 → set
    for (int x : arr1) {                    // 扫描较大数组
        if (!set.add(x)) ans.add(x);       // add()==false → 已存在 → 是公共元素
    }
    return ans;
}

笔记点出一个坑:如果较大数组里有某个公共元素的重复,这段会把它加进去多次(这正是 LC 350「保留重数」的行为)。若你要每个公共值只出现一次(LC 349),把结果收进 set 而不是 list。S2 — 双指针:两个数组都已有序时,双指针齐步走,O(n + m)、O(1) 额外空间。S3 — binary search:若一个数组巨大、另一个很小,把大的排序,再把每个小元素二分进去——O(小 · log 大)。启示还是贯穿全课那条:认出哪种资源是瓶颈,让它来挑工具。

图——节点、边,以及怎么存

图无非是由边连接的节点。在代码里,面向对象的表示是一个携带自身值、邻居和 visited 标记的节点:

class GraphNode {
    int val;
    List<GraphNode> neighbours;   // 无权边
    // List<Pair> neighbours;       // 带权:Pair = (GraphNode, weight)
    boolean visited;

    GraphNode(int x) {
        this.val = x;
        neighbours = new ArrayList<>();
    }
}

对带权图,邻居是一个 (node, weight) 的 Pair 而非光秃秃的节点;若权重按邻居索引,可以用 HashMap 存。两个属性塑造了每一道图题:

• 有向 vs 无向。 有向边是单向的——Twitter 的 follow/unfollow 就是有向(我可以关注你而你不关注我)。无向边是双向的——Facebook 或朋友圈的好友关系两边都成立。
• 连通性与环。 图连通吗?有环吗?DAG(有向无环图)是重要特例:修课的先修关系(必须先修 A 才能学 B)构成一个 DAG,「能不能修完所有课?」——LC 207 Course Schedule——就靠拓扑排序,也就是检测是否存在环来回答。

怎么存图,是一个带取舍的真决策:

矩阵和邻接表是常见的科研表示法;节点对象形式则是面试遍历题里通常拿来操作的那种。选哪个,直接由稀疏程度和你要让哪个操作变便宜决定——正是这整节课在训练的那块识别肌肉。

刷题清单