实战演练：综合题目拆解

这一课你将能做到

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]
}