蓝桥杯错误票据题解：C语言数组标记法找重复与缺失编号

1. 从一道竞赛题看数据处理的基本功

“错误票据”这个题目名字听起来挺接地气，但它背后考察的东西一点都不简单。我第一次接触这道题的时候，觉得不就是找重复和断号嘛，能有多难？结果真正动手写的时候才发现，边界条件、输入格式、数据范围，每一个细节都在考验你对C语言基础功底的掌握程度。

这道题的核心场景是这样的：某单位举办年会，给每位参会者发了一张带编号的票据，编号从1开始连续递增。但因为工作人员疏忽，导致出现了两种错误——某个编号重复了一张，同时某个编号缺失了。你拿到的是所有票据编号的乱序列表，需要找出重复的那个编号和缺失的那个编号。

说白了，这就是一道数组标记+遍历查找的题目。但别小看它，这道题在蓝桥杯历年真题里算是非常经典的一道，因为它同时考察了输入处理、数组运用、边界判断和逻辑思维。很多刚学C语言的同学在这道题上翻车，不是因为算法难，而是因为输入格式没处理好，或者数组开小了导致越界。

这篇文章我会从题目分析、思路拆解、代码实现、常见坑点几个维度，把这道题彻底讲透。不管你是正在准备蓝桥杯，还是想巩固C语言基础，这篇文章都能给你提供可以直接参考的完整方案。

2. 题目核心需求拆解与思路选型

2.1 题目到底在考什么

先把题目翻译成人话。你拿到N行数据，每行可能有多个整数，这些整数就是票据编号。所有编号理论上应该是从1到某个最大值连续排列的，但实际数据中有一个编号出现了两次（重复），有一个编号一次都没出现（缺失）。你的任务就是输出这两个数：先输出重复的编号，再输出缺失的编号。

题目没有告诉你编号的最大值是多少，也没有告诉你一共有多少张票据。你只能从输入数据中自己推断。这就意味着你不能用固定大小的数组去硬编码，必须根据输入动态判断范围。

从算法角度来看，这道题的时间复杂度要求不高，因为数据规模有限。核心操作就是遍历和标记。你可以用一个数组来记录每个编号是否出现过，出现过就标记为1，如果某个编号已经被标记过了又出现一次，那它就是重复的。遍历完所有数据后，再从头扫描标记数组，找到第一个没有被标记的位置，那个下标就是缺失的编号。

2.2 为什么选择数组标记法

有同学可能会想，能不能用排序来解决？把所有编号排序，然后相邻比较，发现相同的就是重复，发现跳过的就是缺失。这个思路没错，但排序的时间复杂度是O(n log n)，而数组标记法只需要O(n)。虽然这道题的数据量不大，两种方法都能过，但从代码简洁度和思维清晰度来说，数组标记法更直接。

另一个考虑是，排序会打乱原始数据的顺序，而数组标记法保留了编号和出现次数之间的直接映射关系。对于这道题来说，编号本身就是天然的下标，用数组标记是最自然的选择。

还有一个关键点：编号的范围。题目中编号从1开始，但最大值不确定。如果你开一个固定大小的数组，比如10000，万一编号超过这个范围就会越界。所以你需要先读入所有数据，找到最大值，再根据最大值来分配数组大小。或者你可以开一个足够大的数组，比如100000，但这样浪费空间。更稳妥的做法是动态分配或者先扫描一遍确定范围。

2.3 输入处理的难点

这道题最大的坑其实在输入格式上。题目说“每行可能有多个整数”，但具体多少个不确定，行数也不确定。你不能简单地用scanf("%d", &n)读一个数就完事，也不能假设每行只有一个数。

常见的处理方式是：用scanf循环读取整数，直到文件结束（EOF）。scanf的一个特性是它会自动跳过空白字符（空格、换行、制表符），所以你不需要关心每行有几个数，只需要一直读就行。读到一个数就处理一个数，直到scanf返回EOF。

但这里有个细节：你需要知道什么时候输入结束。在竞赛环境中，输入通常是从文件重定向的，所以可以用while(scanf("%d", &x) != EOF)来判断。如果是在本地测试，你可能需要手动输入Ctrl+Z（Windows）或Ctrl+D（Linux/Mac）来模拟EOF。

另外，你需要记录所有读入的编号，因为后面要遍历查找缺失的编号。所以你需要一个数组来存储这些编号，同时还需要一个标记数组来记录每个编号是否出现过。

3. 核心细节解析与实操要点

3.1 数组大小的确定策略

数组大小是这道题最容易出问题的地方。如果你开得太小，比如100，而实际编号到了500，就会越界，导致程序崩溃或者结果错误。如果你开得太大，比如1000000，虽然不会越界，但浪费内存，而且在某些对内存有限制的环境中可能出问题。

我的建议是：先读入所有数据到一个临时数组中，同时记录最大值。然后根据最大值来分配标记数组的大小。具体做法是：

int data[10000]; // 假设最多10000个票据 int maxVal = 0; int count = 0; int x; while (scanf("%d", &x) != EOF) { data[count++] = x; if (x > maxVal) maxVal = x; }

这样你就知道了编号的最大值，然后可以分配标记数组：

int *flag = (int *)calloc(maxVal + 1, sizeof(int));

用calloc的好处是它会自动把数组初始化为0，省去了手动清零的步骤。如果你用malloc，就需要用memset手动清零。

提示：在蓝桥杯的评测环境中，通常内存限制是256MB，所以即使你开一个100000的int数组，也只占400KB左右，完全没问题。但养成按需分配的习惯是好事。

3.2 标记与查找的逻辑

有了标记数组之后，逻辑就很清晰了。遍历data数组中的每个编号，如果flag[编号]已经是1，说明这个编号之前出现过，那它就是重复的。否则把flag[编号]设为1。

int duplicate = -1; for (int i = 0; i < count; i++) { if (flag[data[i]] == 1) { duplicate = data[i]; } else { flag[data[i]] = 1; } }

找缺失的编号就更简单了，从1开始遍历到maxVal，找到第一个flag[i] == 0的i，那就是缺失的编号。

int missing = -1; for (int i = 1; i <= maxVal; i++) { if (flag[i] == 0) { missing = i; break; } }

最后输出duplicate和missing即可。

3.3 边界条件与特殊情况

有几个边界条件需要特别注意：

第一，如果重复的编号恰好是最大值，那么缺失的编号可能小于最大值。比如数据是1 2 2 3，最大值是3，重复是2，缺失是4？不对，这里缺失的应该是4吗？实际上如果编号是1到3，但2重复了，3出现了，那缺失的应该是4？不对，如果最大值是3，那编号范围应该是1到3，但2重复了，说明有一个编号缺失了，而3出现了，所以缺失的编号应该是4？这不对，因为如果最大值是3，那编号范围就是1到3，缺失的编号应该在1到3之间。但1出现了，2出现了两次，3出现了，那1到3都出现了，没有缺失啊？但题目说一定有一个缺失，所以这种情况不可能发生。实际上，如果2重复了，那必然有一个编号缺失，而缺失的编号可能是4，因为如果编号范围是1到4，但4没出现，那最大值应该是4才对。所以这里有个逻辑：最大值应该是实际出现的最大编号，但缺失的编号可能大于最大值吗？不可能，因为如果缺失的编号大于最大值，那最大值就不是最大值了。所以缺失的编号一定在1到最大值之间。

第二，如果重复的编号是最小值，比如1重复了，那缺失的编号可能是2或者更大的数。这没问题，遍历查找即可。

第三，输入数据可能有多行，每行多个数，也可能只有一行一个数。用scanf循环读取可以统一处理。

第四，如果输入数据中只有一个数，那不可能有重复和缺失，但题目保证一定有重复和缺失，所以至少有两个数。

4. 完整实操过程与代码实现

4.1 完整代码框架

下面是我在实际做题时使用的完整代码，可以直接编译运行：

#include <stdio.h> #include <stdlib.h> int main() { int data[10000]; int count = 0; int maxVal = 0; int x; // 读取所有输入数据 while (scanf("%d", &x) != EOF) { data[count++] = x; if (x > maxVal) { maxVal = x; } } // 分配标记数组并初始化为0 int *flag = (int *)calloc(maxVal + 1, sizeof(int)); if (flag == NULL) { return 1; } // 标记并查找重复编号 int duplicate = -1; for (int i = 0; i < count; i++) { if (flag[data[i]] == 1) { duplicate = data[i]; } else { flag[data[i]] = 1; } } // 查找缺失编号 int missing = -1; for (int i = 1; i <= maxVal; i++) { if (flag[i] == 0) { missing = i; break; } } // 输出结果 printf("%d %d\n", duplicate, missing); // 释放内存 free(flag); return 0; }

这段代码的逻辑非常清晰：先读数据，再标记，再查找，最后输出。每一步都有明确的意图，没有多余的复杂操作。

4.2 输入输出的实际测试

我用几组测试数据来验证一下：

测试数据1：

5 6 8 11 9 10 12 9

这组数据中，编号有5,6,8,11,9,10,12,9。排序后是5,6,8,9,9,10,11,12。可以看到9重复了，7缺失了。程序输出应该是9 7。

测试数据2：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200

这组数据是1到200连续，但没有重复和缺失，不符合题目要求。所以需要修改一下，比如把100改成101，然后去掉50。这样重复的是101，缺失的是50。

测试数据3：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200

这组数据也是连续的，没有重复和缺失。所以需要手动构造有重复和缺失的数据。

实际上，在竞赛中，测试数据是系统提供的，你不需要自己构造。但为了验证代码的正确性，你可以自己写几组数据测试。

4.3 代码优化与改进

上面的代码虽然能跑，但有几个地方可以优化：

第一，data数组的大小是固定的10000。如果输入数据超过10000个，就会越界。更安全的做法是用动态数组，比如用malloc和realloc来动态扩展。但在竞赛中，通常数据量不会超过10000，所以固定大小也能过。

第二，calloc分配的内存需要检查是否成功。虽然在小内存分配中很少失败，但养成检查的习惯是好的。

第三，输出格式。题目要求输出两个数，中间用空格分隔。我的代码用了printf("%d %d\n", duplicate, missing)，符合要求。

第四，如果输入数据中只有一个数，那maxVal就是那个数，但不可能有重复和缺失，所以这种情况不会出现。

第五，如果重复的编号和缺失的编号相同？不可能，因为重复的编号出现了两次，缺失的编号一次都没出现，它们不可能是同一个数。

5. 常见问题与排查技巧实录

5.1 输入读取不完整

这是最常见的问题。很多同学用scanf("%d", &n)读一个数，然后循环n次读后面的数。但题目没有告诉你n是多少，所以这种方法行不通。正确的做法是用while(scanf("%d", &x) != EOF)一直读到文件结束。

但这里有个坑：如果你在本地测试，手动输入数据后，需要按Ctrl+Z（Windows）或Ctrl+D（Linux/Mac）来触发EOF。如果你直接按回车，程序会一直等待输入，不会结束。

另一个坑是，有些评测环境可能不支持EOF判断，或者输入格式有特殊要求。这时候你可以用while(scanf("%d", &x) == 1)来判断，因为scanf成功读取一个整数时返回1，失败时返回0或EOF。

5.2 数组越界导致崩溃

数组越界是C语言程序崩溃的常见原因。在这道题中，如果你开的标记数组大小小于最大编号，就会越界。比如你开int flag[100]，但编号到了150，访问flag[150]就会越界。

解决方法有两种：一是开足够大的数组，比如int flag[100000]；二是先读数据找到最大值，再动态分配。我推荐第二种，因为更安全，也更符合编程规范。

5.3 重复编号的判断逻辑错误

有些同学在判断重复时，会写成if (flag[data[i]] == 1)，但忘记在else分支中设置flag[data[i]] = 1。这样会导致所有编号都没有被标记，最后找不到重复的编号。

正确的逻辑是：如果flag[data[i]]已经是1，说明之前出现过，记录为重复；否则把flag[data[i]]设为1，表示现在出现了。

5.4 缺失编号的查找范围错误

有些同学在查找缺失编号时，从0开始遍历，但编号是从1开始的，所以0永远缺失，导致输出错误。正确的做法是从1遍历到maxVal。

另外，如果缺失的编号恰好是maxVal + 1，那说明最大值本身是缺失的？不对，如果最大值是maxVal，那它一定出现过，否则它就不是最大值。所以缺失的编号一定在1到maxVal之间。

5.5 常见问题速查表

注意：在竞赛中，输出格式非常重要。多一个空格或少一个换行都可能导致判错。所以一定要严格按照题目要求的格式输出。

5.6 独家避坑技巧

第一个技巧：在本地测试时，可以把输入数据写到一个文本文件中，然后用重定向输入。比如在命令行中运行./program < input.txt，这样就不用手动输入和触发EOF了。

第二个技巧：如果题目没有明确说明编号的最大值，你可以先读一遍数据找到最大值，再分配数组。但这样需要读两遍数据，对于文件输入来说没问题，对于标准输入来说就不行了。所以更通用的做法是开一个足够大的数组，比如100000，然后直接标记。

第三个技巧：在输出之前，可以加一些调试语句，比如打印maxVal、count、duplicate、missing的值，看看是否符合预期。调试完成后记得删除这些语句。

第四个技巧：如果题目要求输出重复编号和缺失编号，但你不确定哪个先输出，可以仔细读题。通常题目会说“先输出重复的编号，再输出缺失的编号”，或者“输出两个数，第一个是重复的，第二个是缺失的”。如果没有明确说明，可以按照常见惯例，先重复后缺失。

6. 从这道题延伸出的编程思维

这道题虽然简单，但它体现了一种非常重要的编程思维：用空间换时间。通过开一个标记数组，把查找重复和缺失的时间复杂度从O(n²)降低到O(n)。这种思维在很多算法题中都有应用，比如哈希表、桶排序等。

另一个值得思考的点是输入处理的通用性。在实际开发中，你经常需要处理不确定格式的输入。用scanf循环读取是一种通用的方法，但也要注意它的局限性，比如无法处理字符串中的空格等。对于更复杂的输入，可能需要用fgets逐行读取，然后再用sscanf或字符串分割来处理。

还有一个点是边界条件的处理。这道题中，编号从1开始，最大值不确定，缺失的编号一定在1到最大值之间。这些边界条件如果不注意，很容易写出错误的代码。在实际开发中，边界条件往往是bug的重灾区，需要特别小心。

最后，这道题也提醒我们，代码的可读性很重要。虽然你可以把所有的逻辑写在一行里，但那样不利于调试和维护。把逻辑拆分成清晰的步骤，加上适当的注释，不仅方便自己理解，也方便别人阅读。

7. 个人实操体会与建议

我在第一次做这道题的时候，最大的问题出在输入处理上。我当时用scanf("%d", &n)读了一个数，然后以为n是票据的数量，结果发现n其实是第一个票据编号。后来才明白，题目根本没有告诉你票据数量，你需要一直读到文件结束。

另一个问题是数组大小。我一开始开了一个int flag[1000]，结果测试数据中编号到了1500，导致越界。后来改成int flag[100000]，虽然浪费空间，但至少不会越界。再后来学会了先读数据找最大值，再动态分配，感觉更优雅。

还有一个细节是，我在判断重复时，一开始写成了if (flag[data[i]] == 1) duplicate = data[i];，但忘记在else中设置flag[data[i]] = 1。结果所有编号都没有被标记，最后找不到重复的编号。这个bug我调了半个小时才找到，教训深刻。

所以我的建议是：写代码之前先把逻辑想清楚，最好在纸上画一画流程图。写完之后用几组测试数据验证一下，特别是边界情况。如果时间允许，可以写一个简单的暴力程序来对拍，确保结果正确。

对于正在准备蓝桥杯的同学，我建议多刷历年真题，每道题都自己动手写一遍，不要只看题解。写完之后再对照别人的代码，看看有没有可以改进的地方。这样进步最快。

这道题虽然简单，但它是很多算法题的基础。掌握了数组标记法，你就能解决很多类似的问题，比如找第一个缺失的正整数、找重复元素等。所以不要因为它简单就跳过，认真做一遍，收获会比你想象的多。