实战演练：综合题目拆解

这一课你将能做到

1. 独立拆解一道综合题，从读题到 AC 的完整流程
2. 识别题目中的多个模式并组合使用
3. 在规定时间内写出能通过所有测试用例的代码

为什么要学

实战是检验学习的唯一标准。看懂了不等于会了，能 AC 才是真的会。这一课带你走完一道综合题的完整流程：读题 → 分析 → 选择算法 → 编码 → 调试 → 优化。

人话：就像考试做题，不是背公式，是理解题目要什么，选择合适的工具，一步步算出来。

先建立图像

读题 → 提取信息 → 归类模式 → 选择算法 → 估算复杂度 → 编码 → 测试 → 提交

例：找到数组中出现次数前 K 高的元素
    ↓
    统计频率（哈希表）→ Top K（堆）→ O(n log k)

跟着做

步骤 1：读题并提取关键信息

题目：给定一个非空整数数组，返回其中出现频率前 K 高的元素。

提取：

• 输入：int[] nums, int k
• 输出：int[]（前 K 高频率元素）
• 约束：1 ≤ k ≤ 不同元素个数
• 关键词：「频率」→ 哈希表；「前 K 高」→ 堆

步骤 2：分析并选择算法

方案 A：排序法。统计频率后按频率排序。O(n log n)，n 大时可能 TLE。 方案 B：堆法。统计频率，用小顶堆维护前 K 大。O(n log k)，更优。

选择：方案 B。n 可能到 10^5，O(n log n) 是 10^6，可以过；但 O(n log k) 更优。

步骤 3：编码

import java.util.*;

public class Main {
    public static int[] topKFrequent(int[] nums, int k) {
        // 步骤 1：统计频率
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        
        // 步骤 2：小顶堆，保持堆大小为 k
        PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>(
            Comparator.comparingInt(Map.Entry::getValue)
        );
        
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            heap.offer(entry);
            if (heap.size() > k) {
                heap.poll(); // 弹出频率最小的
            }
        }
        
        // 步骤 3：提取结果
        int[] res = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            res[i] = heap.poll().getKey();
        }
        return res;
    }
    
    public static void main(String[] args) {
        int[] nums = {1,1,1,2,2,3};
        int k = 2;
        int[] res = topKFrequent(nums, k);
        System.out.println(Arrays.toString(res)); // [1, 2]
    }
}

步骤 4：测试边界

// 测试用例
public static void main(String[] args) {
    // 正常情况
    System.out.println(Arrays.toString(topKFrequent(new int[]{1,1,1,2,2,3}, 2))); // [1,2]
    
    // k = 1
    System.out.println(Arrays.toString(topKFrequent(new int[]{1}, 1))); // [1]
    
    // 所有元素频率相同
    System.out.println(Arrays.toString(topKFrequent(new int[]{1,2}, 2))); // [2,1] 或 [1,2]
    
    // 大量重复
    int[] big = new int[100000];
    Arrays.fill(big, 1);
    System.out.println(Arrays.toString(topKFrequent(big, 1))); // [1]
}

步骤 5：复杂度分析

• 统计频率：O(n)
• 堆操作：O(n log k)
• 提取结果：O(k log k)
• 总复杂度：O(n log k)
• 空间复杂度：O(n)（哈希表）+ O(k)（堆）

步骤 6：优化与变体

变体 1：如果要求频率相同的按数值升序？

PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>(
    (a, b) -> a.getValue().equals(b.getValue()) 
        ? a.getKey() - b.getKey() 
        : a.getValue() - b.getValue()
);

变体 2：如果 n 非常大，内存不够存所有频率？

用外部排序或分治，或改用 TreeMap 维护频率区间。

步骤 7：第二道实战——岛屿数量

题目：给定一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算岛屿的数量。岛屿被水包围，由相邻陆地（水平或垂直）连接形成。

分析：

• 关键词：「二维网格」「相邻」「连接」→ 图遍历
• 模式：DFS/BFS 找连通分量
• 复杂度：O(m×n)，必须访问每个格子

public class Main {
    static int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    
    public static int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int m = grid.length, n = grid[0].length, count = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j, m, n);
                    count++;
                }
            }
        }
        return count;
    }
    
    static void dfs(char[][] grid, int i, int j, int m, int n) {
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') return;
        grid[i][j] = '0'; // 沉没陆地，标记已访问
        for (int[] d : dirs) {
            dfs(grid, i + d[0], j + d[1], m, n);
        }
    }
    
    public static void main(String[] args) {
        char[][] grid = {
            {'1','1','0','0','0'},
            {'1','1','0','0','0'},
            {'0','0','1','0','0'},
            {'0','0','0','1','1'}
        };
        System.out.println(numIslands(grid)); // 3
    }
}

变体：如果网格巨大（10^6×10^6），递归 DFS 会栈溢出。改用迭代+BFS：

import java.util.*;

public class Main {
    static int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    
    public static int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int m = grid.length, n = grid[0].length, count = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    bfs(grid, i, j, m, n);
                    count++;
                }
            }
        }
        return count;
    }
    
    static void bfs(char[][] grid, int i, int j, int m, int n) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{i, j});
        grid[i][j] = '0';
        
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            for (int[] d : dirs) {
                int ni = curr[0] + d[0], nj = curr[1] + d[1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == '1') {
                    grid[ni][nj] = '0';
                    queue.offer(new int[]{ni, nj});
                }
            }
        }
    }
    
    public static void main(String[] args) {
        char[][] grid = {
            {'1','1','0'},
            {'1','0','0'},
            {'0','0','1'}
        };
        System.out.println(numIslands(grid)); // 2
    }
}

讲清楚要点

1. 读题是第一要务：关键词决定模式。本题「频率」→哈希表，「前 K」→堆。
2. 复杂度预判：n=10^5 时，O(n log n) 和 O(n log k) 都能过，但后者更优。
3. 堆的选择：前 K 大用小顶堆（弹最小），前 K 小用大顶堆（弹最大）。
4. 代码结构：分步注释，每步对应一个算法步骤，便于调试。

你可能会懵的地方

• 为什么用小顶堆不是大顶堆？ 小顶堆的堆顶是「前 K 大中最小的」，新元素比它大就替换，这样堆里始终保持前 K 大。

• PriorityQueue 怎么存 Entry？ Map.Entry<Integer, Integer> 是键值对。比较器比较 getValue()（频率）。

• k 大于不同元素个数怎么办？ 题目保证 1 ≤ k ≤ 不同元素个数。不保证的话加 k = Math.min(k, count.size())。

• 结果顺序重要吗？ 题目说「按频率从高到低」，我们堆弹出是从小到大，所以倒序填数组。

• 怎么验证正确性？ 对拍：写一个暴力解法（排序），随机生成数据对比两种方法的结果。

错法对照

错法	问题	正解
用大顶堆求前 K 大	堆里留的是最小的 K 个	用小顶堆，弹最小
不排序直接返回堆元素	结果顺序不对	倒序填数组或改用大顶堆
忽略频率相同的情况	结果不稳定	比较器加第二关键字
用数组代替哈希表统计频率	数值范围大时 MLE	哈希表按需分配
堆大小不控制	O(n log n) 退化	严格控制堆大小为 k

卡点急救

1. 结果顺序不对：打印堆中所有元素，确认比较器逻辑。
2. k=1 时结果错误：检查是否处理了单元素数组。
3. 大数据 TLE：确认没有不必要的排序，堆大小是否严格为 k。

面试常问

• 这道题的最优复杂度是多少？ O(n log k)，用堆。如果 k 接近 n，O(n log n) 也可以接受。

• 如果数据流是实时的怎么办？ 用两个堆（大顶堆+小顶堆）维护中位数，或用平衡树（TreeMap）。

• 怎么扩展到分布式环境？ 分治：每台机器统计局部频率，合并时用堆归并。

自测三问

1. 为什么前 K 大用小顶堆而不是大顶堆？
2. 这道题的空间复杂度是多少？
3. 如果要求频率相同的元素按数值升序，比较器怎么写？

小结一句话

实战的关键是读题归类、选择算法、分步编码、测试边界；掌握完整流程，任何题目都能拆解。

延伸

• LeetCode 347：前 K 个高频元素
• 下一课：毕业设计——实现一个简化版在线判题系统。