蓝桥杯算法实战：从去重排序到质数拆分的解题思维与Java实现

1. 从两道真题看蓝桥杯的算法考察逻辑

最近在带几个学生准备蓝桥杯，发现他们刷题时有个通病：拿到题目就埋头写代码，结果要么超时，要么逻辑漏洞百出。特别是像“质数拆分”和“明明的随机数”这类经典题目，看似基础，实则暗藏玄机，非常能考察一个选手对算法和数据结构的理解深度。今天我就结合这两道题，聊聊蓝桥杯Java组解题时，除了“能跑通”之外，更应该关注的那些东西——比如如何把一道题拆解成清晰的步骤，如何选择合适的数据结构，以及如何写出既高效又健壮的代码。这不仅仅是应付比赛，更是锻炼工程思维的好机会。

“质数拆分”本质上是一个动态规划问题，但披着数论的外衣，你需要先筛出质数，再将其视为“物品”进行组合。而“明明的随机数”则是考察对Java集合框架的熟练运用和去重排序的基本功。两道题一难一易，组合在一起，恰好覆盖了从基础语法到中等难度算法的过渡。接下来，我会先带大家吃透“明明的随机数”这道开胃菜，建立信心和规范，再深入“质数拆分”的核心，拆解其动态规划的建模过程。你会发现，把思路理清，比盲目敲代码要重要得多。

2. “明明的随机数”：巩固基础与规范编码

这道题可以说是蓝桥杯乃至许多OJ平台的“Hello World”级算法题。题目要求很简单：输入N个随机整数，去重后排序输出。很多新手觉得用Arrays.sort()和一层循环去重就完事了，但这样往往只能过样例，在性能或边界条件上会栽跟头。我们先从最直接的思路开始，逐步优化。

2.1 问题重述与输入输出分析

题目描述通常为：明明生成了N个1到1000之间的随机整数，请你删去其中重复的数字，并按从小到大的顺序输出。输入有两行，第一行是随机整数的个数N，第二行是N个用空格隔开的整数。

这里有几个关键点需要预先明确，这也是很多同学第一次提交就“Wrong Answer”的原因：

1. N的范围：题目虽未明确，但根据经验，N可能很大（比如10^5）。这意味着O(N²)的暴力去重（双重循环比较）一定会超时。
2. 去重与排序的优先级：必须先完成去重，再对去重后的结果排序。如果先排序再去重，在编码上会更简单，但逻辑上依然是两个独立步骤。
3. 输出格式：通常要求每个数字占一行，或者用空格隔开在一行内输出，务必看清题目要求。

一个健壮的程序必须处理这些边界。例如，当N=0时，程序不应该崩溃，而应该无输出或输出空行。输入的数字可能不是严格在1-1000之间，但只要在int范围内，我们的算法就应该能处理。

2.2 方案对比：从暴力到优雅

我们先看看几种常见的实现方案，并分析其优劣。

方案一：排序后遍历去重这是最直观的方法。先使用Arrays.sort()对输入数组进行排序，时间复杂度为O(N log N)。排序后，相同的数字会相邻。然后遍历数组，只输出与上一个输出不同的数字。

import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } Arrays.sort(arr); // 处理边界：如果数组为空，则直接结束 if (n == 0) { return; } // 输出第一个元素 System.out.println(arr[0]); for (int i = 1; i < n; i++) { // 如果当前元素不等于前一个元素，则输出 if (arr[i] != arr[i - 1]) { System.out.println(arr[i]); } } } }

优点：逻辑清晰，代码简短，利用排序特性自然去重。缺点：修改了原始输入数组（排序操作），如果后续还需要原数组，则需拷贝。另外，当数字范围已知且较小时，有更优解。

方案二：利用布尔数组标记（桶排序思想）由于题目限定了数字范围（1-1000），我们可以利用这个信息。创建一个大小为1001的布尔数组boolean[] flag = new boolean[1001]。遍历输入数字，以该数字为下标，将对应位置标记为true。最后，遍历flag数组，下标值即为排序去重后的结果。

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); boolean[] exists = new boolean[1001]; // 下标0-1000 for (int i = 0; i < n; i++) { int num = sc.nextInt(); exists[num] = true; // 标记该数字存在 } for (int i = 1; i <= 1000; i++) { // 题目范围是1-1000 if (exists[i]) { System.out.println(i); } } } }

优点：时间复杂度为O(N+M)，其中M是数值范围（1001），在N很大时效率极高，且天然完成了排序和去重。缺点：严重依赖于数值范围已知且不大的前提。如果数字范围是整型，这种方法会消耗巨大内存（约2^31个布尔值，不可行）。

方案三：使用TreeSet（最符合Java风格的解法）TreeSet是Java集合框架中基于红黑树实现的有序集合，它自动保证元素唯一且按自然顺序（或指定比较器）排序。

import java.util.Scanner; import java.util.TreeSet; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); TreeSet<Integer> set = new TreeSet<>(); for (int i = 0; i < n; i++) { set.add(sc.nextInt()); // 添加操作自动去重，TreeSet自动排序 } for (Integer num : set) { System.out.println(num); } } }

优点：代码极其简洁，完全将去重和排序的逻辑委托给TreeSet，体现了Java高级API的便捷性。时间复杂度为O(N log N)，与排序法相当。缺点：对于算法竞赛，需要了解其底层是红黑树，每次插入是O(log N)。在极端追求性能的场景下，可能不如方案二。但绝大多数情况下，这是最佳选择。

提示：在蓝桥杯等竞赛中，如果题目明确数值范围小（如本题的1-1000），方案二（桶标记法）是首选，因为它最快且稳定。如果不确定范围或范围很大，方案三（TreeSet）是最优雅和通用的选择。方案一则是理解基础算法流程的好例子。

2.3 常见“坑点”与调试心得

即便思路正确，实现时也可能踩坑。这里分享几个我学生常犯的错误：

1. 输入读取问题：使用Scanner时，在读取完数字后，如果下一行还有输入（比如字符串），要注意用nextLine()吸收掉换行符。本题只有数字，问题不大。
2. 输出格式问题：题目要求每行一个数，就不能输出成一行用空格隔开。务必仔细阅读输出描述。有时最后一个数字后面不能有多余空格或换行，需要使用StringBuilder进行拼接控制。
3. 边界条件处理：当N=0或1时，你的循环还能正常工作吗？Arrays.sort()对空数组排序不会报错，但后续的arr[0]就会数组越界。方案二的循环从1开始，也需要注意N=0的情况。
4. 性能考量：虽然本题数据量可能不大，但养成好习惯。避免在循环内进行字符串拼接（如s += num + “\n”），因为会创建大量临时对象。使用StringBuilder或直接System.out.println是更好的选择。

在实际编码中，我建议先写方案三，因为它最不容易出错。如果追求极致性能，再考虑根据题目条件换用方案二。理解每种方案背后的数据结构（数组、红黑树），比记住代码更重要。

3. “质数拆分”：动态规划与数论的结合

如果说“明明的随机数”是热身，那“质数拆分”就是正餐了。这道题完美地结合了数论（质数筛法）和动态规划（背包问题），是蓝桥杯考查综合能力的典型题目。题目通常描述为：将某个正整数拆分为若干个不同的质数之和，问有多少种拆分方法。例如，2019可以被拆分成多少种不同的质数组合？

看到“拆分”、“多少种方法”，有经验的选手立刻会联想到动态规划中的“组合问题”。但这里的“物品”不是题目直接给出的，而是需要我们自己先求出来——所有小于目标数的质数。因此，解题分为两个清晰的阶段：第一阶段筛质数，第二阶段动态规划计数。

3.1 第一阶段：高效筛选质数

动态规划需要质数作为“物品”列表。如何快速得到所有小于目标数N的质数？这里就需要用到高效的筛法。最著名的有两种：埃拉托斯特尼筛法（埃氏筛）和欧拉筛（线性筛）。

埃氏筛（Eratosthenes Sieve）原理很简单：从2开始，将每个质数的倍数标记为合数。

public static List<Integer> getPrimes(int limit) { boolean[] isPrime = new boolean[limit + 1]; Arrays.fill(isPrime, true); isPrime[0] = isPrime[1] = false; // 0和1不是质数 List<Integer> primes = new ArrayList<>(); for (int i = 2; i <= limit; i++) { if (isPrime[i]) { primes.add(i); // i是质数 // 标记i的所有倍数为合数 // 优化：从i*i开始标记，因为小于i*i的合数已被更小的质数标记过 if ((long) i * i <= limit) { for (int j = i * i; j <= limit; j += i) { isPrime[j] = false; } } } } return primes; }

时间复杂度：O(N log log N)，对于N=2019绰绰有余，甚至N=10^6也很快。优点：实现简单，易于理解和记忆。缺点：一个合数会被多个质数标记，有重复操作。

欧拉筛（线性筛）欧拉筛保证了每个合数只被其最小的质因数标记一次，从而达到线性时间复杂度O(N)。

public static List<Integer> getPrimesLinear(int limit) { boolean[] isPrime = new boolean[limit + 1]; Arrays.fill(isPrime, true); isPrime[0] = isPrime[1] = false; List<Integer> primes = new ArrayList<>(); for (int i = 2; i <= limit; i++) { if (isPrime[i]) { primes.add(i); } // 用当前已得到的质数 primes.get(j) 去标记合数 for (int j = 0; j < primes.size() && i * primes.get(j) <= limit; j++) { isPrime[i * primes.get(j)] = false; // 关键：如果i能被当前质数整除，则跳出循环 // 保证每个合数只被其最小质因子标记一次 if (i % primes.get(j) == 0) { break; } } } return primes; }

对于本题（N=2019），两种筛法时间差异微乎其微。但在面对更大数据（如N=10^7）时，欧拉筛的优势会体现出来。在竞赛中，如果对筛法不熟，用埃氏筛足矣，代码更不容易写错。

注意：在动态规划中，我们需要的质数列表是primes。同时，我们可能还需要快速判断一个数是否为质数，这时isPrime布尔数组就派上用场了。在“质数拆分”问题中，我们通常只需要列表。

3.2 第二阶段：动态规划建模与实现

拿到质数列表后，问题转化为：给定一个目标总和S（如2019），和一系列互不相同的“物品”（质数），每个物品只能使用一次（不同质数），求恰好装满容量S的背包，有多少种组合方式？

这是一个经典的0-1背包计数问题。定义状态dp[i][j]为：考虑前i个质数，组成总和为j的方案数。状态转移方程如下：

• 如果不选第i个质数p：方案数等于前i-1个质数组成j的方案数，即dp[i][j] = dp[i-1][j]。
• 如果选第i个质数p（前提是j >= p）：方案数等于前i-1个质数组成j-p的方案数，即dp[i][j] += dp[i-1][j-p]。

初始化：dp[0][0] = 1，表示用0个质数组成0，有1种方案（什么都不选）。其他dp[0][j] (j>0) = 0。

最终答案：dp[n][S]，其中n是质数的个数。

空间优化（滚动数组）由于dp[i][j]只依赖于dp[i-1][...]，我们可以将二维数组压缩成一维数组dp[j]。但需要注意，为了确保每个质数只使用一次，内层循环j需要从大到小遍历。

public static long countPrimeSplits(int target) { List<Integer> primes = getPrimes(target); // 获取所有小于等于target的质数 long[] dp = new long[target + 1]; dp[0] = 1; // 初始化：总和为0的方案数为1 for (int prime : primes) { // 0-1背包，逆序更新 for (int j = target; j >= prime; j--) { dp[j] += dp[j - prime]; } } return dp[target]; }

为什么内层要逆序？这是0-1背包空间优化的关键。如果正序遍历，当更新dp[j]时，dp[j - prime]可能已经在同一轮（考虑当前质数时）被更新过了，这意味着我们可能重复使用了当前质数多次，变成了“完全背包”问题。逆序遍历保证了在更新dp[j]时，dp[j - prime]还是基于“未考虑当前质数”的状态，从而每个质数最多被使用一次。

3.3 完整代码实现与测试

将两部分结合起来，并处理输入输出，完整的解题代码如下：

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int target = sc.nextInt(); // 例如输入 2019 System.out.println(countPrimeSplits(target)); } // 埃氏筛获取质数列表 public static List<Integer> getPrimes(int limit) { boolean[] isPrime = new boolean[limit + 1]; Arrays.fill(isPrime, true); isPrime[0] = isPrime[1] = false; List<Integer> primes = new ArrayList<>(); for (int i = 2; i <= limit; i++) { if (isPrime[i]) { primes.add(i); if ((long) i * i <= limit) { for (int j = i * i; j <= limit; j += i) { isPrime[j] = false; } } } } return primes; } // 动态规划计算拆分方案数 public static long countPrimeSplits(int target) { List<Integer> primes = getPrimes(target); long[] dp = new long[target + 1]; dp[0] = 1; for (int prime : primes) { for (int j = target; j >= prime; j--) { dp[j] += dp[j - prime]; } } return dp[target]; } }

测试与验证：

• 输入7，质数有[2,3,5,7]。拆分方式有：7, 2+5, 2+2+3? (不行，2重复了)。实际上，7=7, 2+5。答案是2。程序输出2。
• 输入10，质数[2,3,5,7]。拆分：2+3+5=10, 3+7=10, 2+2+...（不允许重复）。答案是2。程序输出2。
• 输入2019，这是一个较大的数，需要程序有较好的效率。运行上述代码，可以很快得到结果（具体数值需运行程序）。

3.4 深入思考：不同与重复的边界

这道题有一个非常关键的约束：“不同的质数”。这直接决定了我们使用0-1背包模型。如果题目改为“可重复使用同一个质数”，那就变成了完全背包计数问题，其动态规划的内层循环就需要正序遍历了。

// 假设质数可以重复使用（完全背包问题） public static long countPrimeSplitsUnlimited(int target) { List<Integer> primes = getPrimes(target); long[] dp = new long[target + 1]; dp[0] = 1; for (int prime : primes) { // 完全背包，正序更新 for (int j = prime; j <= target; j++) { dp[j] += dp[j - prime]; } } return dp[target]; }

仅仅是一个遍历顺序的区别，问题的本质就变了。在比赛时，一定要像这样仔细审题，抓住“不同”、“重复”、“顺序有关/无关”这些关键词，它们直接决定了算法模型的选择。

另一个容易混淆的点是“组合”与“排列”。本题是组合问题（2+3+5和3+2+5被视为同一种），所以我们的物品（质数）是放在外层循环的。如果是排列问题（顺序不同视为不同方案），则需要把目标总和放在外层循环，物品放在内层。理解这些细微差别，才能灵活应对变种题目。

4. 算法竞赛中的实战技巧与心态

通过这两道题，我们不仅学习了具体解法，更重要的是一种系统化的解题思维。在蓝桥杯或任何算法竞赛中，时间有限，压力大，如何快速且正确地解决问题？我结合自己的参赛和教学经验，分享几点心得。

4.1 四步解题法：读、析、设、码

1. 读题与抽象（5分钟）：这是最关键的一步。逐字逐句读题，用笔划出关键约束：数据范围（N, M的大小）、特殊条件（是否重复、是否有序）、输入输出格式。像“质数拆分”中的“不同质数”，就是核心约束。将实际问题抽象成数学模型或已知算法问题（背包、搜索、图论等）。
2. 复杂度分析与算法设计（5-10分钟）：根据数据范围反推可接受的算法复杂度。例如，N≤20可能用指数级搜索；N≤1000可能用O(N²)动态规划；N≤10^5通常需要O(N log N)或O(N)的算法。设计算法步骤，在草稿纸上画出状态转移或流程。
3. 细节设计与边界考虑（5分钟）：设计数据结构（用数组还是集合？），确定循环边界，思考初始化状态。考虑极端情况：空输入、最大/最小输入、结果为0或1的情况。为这些情况设计测试样例。
4. 编码与调试（剩余时间）：将设计翻译成代码。优先保证代码清晰可读，使用有意义的变量名。写完后，用自己设计的边界样例和题目样例进行测试。如果出错，使用打印语句或调试器，定位问题，是算法逻辑错误还是边界处理不当？

很多同学把大部分时间花在编码和调试上，往往是因为前两步没做好。磨刀不误砍柴工，清晰的思路能节省大量时间。

4.2 Java选手的武器库与避坑指南

作为Java选手，我们有一些独特的优势和需要特别注意的“坑”。

优势武器库：

• 丰富的集合框架：ArrayList,LinkedList,HashSet,TreeSet,HashMap,PriorityQueue等。像“明明的随机数”用TreeSet，复杂去重计数用HashMap，能极大简化代码。
• 强大的工具类：Arrays.sort(),Collections.sort(),Math类下的各种函数。
• StringBuilder：在需要频繁拼接字符串时（如输出结果），务必使用StringBuilder，直接使用+连接在循环中会带来巨大的性能开销。

常见“坑点”：

• 输入输出效率：当输入数据量极大（10^5以上）时，Scanner可能会成为性能瓶颈。此时应换用BufferedReader。

BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] params = br.readLine().split(" "); int n = Integer.parseInt(params[0]);

• 整数溢出：这是最隐蔽的Bug之一！两个int相乘，即使结果用long接收，乘法运算本身也可能已经溢出。例如计算i * i时，如果i接近10^5，i*i就超过int范围了。解决办法是提前将操作数转为long：(long) i * i。在“质数拆分”的dp计数中，方案数也可能超过int范围，所以dp数组要用long。
• 递归深度：Java默认的栈深度可能无法支持很深的递归（如DFS搜索深度超过1万层）。非尾递归的深搜要考虑用栈数据结构手动模拟，或者尝试迭代解法。
• 内存限制：蓝桥杯通常内存限制为128MB或256MB。要估算数组大小，例如一个int[100000][100000]的二维数组绝对会内存超限。在必须使用二维DP时，考虑是否能滚动数组优化成一维。

4.3 从刷题到精通：如何有效练习

最后，谈谈练习方法。盲目刷几百道题，不如精做几十道。

1. 一题多解：就像我们对“明明的随机数”做的，尝试用多种方法解决同一问题，并分析时空复杂度差异。这能加深你对数据结构和算法的理解。
2. 举一反三：做完“质数拆分”，可以去找其他背包问题（01背包、完全背包、多重背包）的题目，或者找其他涉及质数筛法的题目。建立知识之间的联系。
3. 总结模板与套路：将常见的算法写成自己熟悉的“模板”，例如二分查找、快速排序、DFS/BFS框架、并查集、Dijkstra算法等。但记住，模板是思考的起点，不是终点，要根据具体问题调整。
4. 参加模拟赛与复盘：定期参加限时模拟赛，锻炼在压力下解题的能力。赛后一定要复盘，不仅看错题，还要看那些做对了但耗时很长的题，思考是否有更优解。

算法学习是一场马拉松，核心是锻炼逻辑思维和问题解决能力。蓝桥杯是一个很好的舞台，但更重要的是通过备赛过程获得实实在在的成长。希望这篇结合具体真题的长文，能帮你理清思路，在下次遇到问题时，能更快地抓住本质，写出既正确又优雅的代码。