★ FEATURED ARTICLE 1. 这道题到底在考什么第一次看到“错误票据”这个题目名很多人会以为是一道跟财务、发票相关的业务题。实际上它是一道非常经典的数组处理与逻辑推理题出现在2013年第四届蓝桥杯省赛的C语言组里。题目本身不长但信息密度很高考察的是你对数据的敏感度、对边界条件的把控以及能不能用最朴素的工具解决看起来有点绕的问题。先把题目核心意思还原一下。某单位发年终福利用票据记录每个人的编号。编号是连续的正整数从某个最小值开始到某个最大值结束理论上中间不会断号也不会重复。但实际回收票据时出了两个问题第一有一张票据的编号重复了也就是某个编号出现了两次第二有一张票据缺失了也就是某个编号一次都没出现。现在你手里有一堆乱序的票据编号需要找出重复的那个编号和缺失的那个编号。输入格式通常是先给一个整数N表示接下来有N行数据每行有若干个编号编号之间用空格分隔。所有编号打乱顺序混在一起。输出要求是先输出重复的编号再输出缺失的编号中间用空格隔开。这道题在当年难住了不少刚学C语言的同学原因不在于算法有多高深而在于几个容易踩坑的地方数据量不确定、输入行数和每行个数不固定、编号范围未知、需要同时处理重复和缺失两个目标。很多人一上来就想排序排完序再遍历思路没错但实现细节上容易翻车。我后来带过几个刚入门的朋友做这道题发现大家卡住的地方出奇地一致不知道怎么读入不定长数据、不知道怎么在不开超大数组的情况下标记状态、不知道怎么处理“缺失”和“重复”同时存在的情况。下面我就按实际操作的顺序把这道题从思路到代码到避坑完整拆一遍。2. 核心思路拆解与方案选型2.1 为什么排序是最直观的入口拿到一堆乱序数字要找重复和缺失最自然的想法就是先让它们变得有序。排序之后重复的数字会挨在一起缺失的数字会表现为相邻两个数之间的“断层”。这个思路非常符合人的直觉代码写起来也直接。假设排序后的序列是1 2 3 3 5 6你一眼就能看出3重复了4缺失了。程序要做的就是遍历这个有序序列比较相邻两个元素如果相等说明当前这个数是重复的如果后一个减前一个等于2说明中间缺了一个数缺失的就是前一个数加1。这个方案的优势是逻辑清晰、容易验证。缺点是排序本身有时间开销如果编号数量很大比如十万级别用冒泡排序就会超时。但在蓝桥杯这道题的规模下编号数量通常不会特别夸张用C标准库里的qsort或者自己写个快速排序都完全够用。2.2 不排序行不行标记数组方案除了排序还有一个更“程序员”的做法用一个标记数组。因为编号是连续的正整数范围虽然未知但一定在某个区间内。我们可以先找出所有编号里的最大值和最小值然后开一个大小为“最大值减最小值加一”的数组初始全为0。遍历所有编号把对应位置加一。最后再遍历这个标记数组值为0的位置对应缺失编号值为2的位置对应重复编号。这个方案的时间复杂度是线性的比排序更快而且逻辑同样简单。但它有一个前提编号的最大值不能太大。如果编号范围是1到100000开一个100001的数组完全没问题但如果编号范围是1到10亿这个方案就废了内存扛不住。在实际比赛环境中题目通常会给出数据范围的暗示或者测试数据不会故意卡内存。所以标记数组方案是可行的而且写起来比排序更短。我个人的习惯是如果题目明确说了编号范围或者通过输入能判断范围可控优先用标记数组如果范围完全未知且可能很大就用排序。2.3 两种方案的对比与选择建议对比维度排序方案标记数组方案时间复杂度O(n log n)O(n range)空间复杂度O(n)O(range)实现难度中等需要写排序或调用qsort简单直接下标访问适用场景编号范围未知或极大编号范围可控且不太大边界风险排序写错、相邻比较漏情况数组开太小、最大值判断错误从比赛实战角度我建议两种都掌握。如果时间紧直接上标记数组因为代码短、出错概率低。如果担心内存就用排序。这道题的数据规模用哪种都能过关键是选一个你写得最顺的。提示不管选哪种方案都要先完整读入所有数据再处理。不要边读边判断因为重复和缺失的判断需要全局信息。3. 输入处理最容易翻车的第一关3.1 为什么输入格式让人头疼这道题的输入格式是第一行一个整数N表示后面有N行数据。但每行有多少个编号是不确定的可能一行一个也可能一行十个。编号之间用空格分隔行末可能有也可能没有多余空格。这种“行数固定但每行个数不定”的格式用scanf直接读会遇到麻烦。很多人的第一反应是用scanf(%d, x)循环读但这样读完之后不知道什么时候该换行也不知道总共读了多少个数。更麻烦的是如果直接用scanf读N行每行用gets或者fgets读字符串再解析又容易在空格和换行上出错。3.2 推荐做法逐字符读取加手动解析我试过几种读入方式最稳的是用getchar逐字符读取遇到数字字符就累积遇到非数字字符就结算一个数。这种方式不依赖行结构不管一行有多少个数、空格怎么分布都能正确读出来。具体逻辑是这样的用一个循环不断读字符如果读到的是数字就把它累加到当前数值里如果读到的是空格、换行或者文件结束符并且当前数值有效就把这个数存进数组然后重置当前数值。这样读完之后数组里就是所有编号顺序无所谓。#include stdio.h int data[100005]; int cnt 0; int main() { int N; scanf(%d, N); getchar(); // 吃掉第一行末尾的换行符 int ch; int num 0; int hasNum 0; while ((ch getchar()) ! EOF) { if (ch 0 ch 9) { num num * 10 (ch - 0); hasNum 1; } else { if (hasNum) { data[cnt] num; num 0; hasNum 0; } } } // 处理文件末尾可能残留的最后一个数 if (hasNum) { data[cnt] num; } // 后续处理... return 0; }这段代码的关键点在于hasNum标记。如果没有这个标记连续遇到多个空格或换行时会错误地存入0。另外getchar读到EOF时循环结束但最后一个数可能还没结算所以循环外要再判断一次。3.3 常见输入坑与规避方法第一个坑是scanf读N之后留下的换行符。如果你紧接着用getchar读数据第一个读到的就是换行符虽然不会造成错误但逻辑上要清楚。我习惯在scanf后面加一个getchar()把换行吃掉这样后续读取更干净。第二个坑是行末空格。有些测试数据的行末有空格有些没有。用逐字符解析的方式完全不受影响因为空格和换行在解析逻辑里是同等对待的。第三个坑是文件末尾没有换行。如果最后一个编号后面直接是EOF没有换行符那么循环结束时hasNum还是1需要在循环外补一次存入。这个细节很多人会漏掉导致最后一个数丢失进而影响缺失编号的判断。注意数组大小要开够。虽然题目没说编号数量上限但蓝桥杯的测试数据通常不会超过十万个编号。开一个100005的数组是安全的。如果你不确定可以开到1000005内存也完全够。4. 排序方案完整实现与细节剖析4.1 用qsort排序的写法C标准库里的qsort是处理这道题最省事的排序工具。它的函数签名是void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *))。对于整数数组比较函数这样写int cmp(const void *a, const void *b) { return (*(int *)a) - (*(int *)b); }调用的时候传数组首地址、元素个数、元素大小和比较函数qsort(data, cnt, sizeof(int), cmp);排完之后数组就是升序的。接下来遍历一遍找重复和缺失。4.2 遍历找重复与缺失的逻辑遍历从第二个元素开始每次比较当前元素和前一个元素。有三种情况当前元素等于前一个元素说明当前这个数是重复的。当前元素减前一个元素等于2说明中间缺了一个数缺失的是前一个元素加1。当前元素减前一个元素等于1正常连续什么都不做。如果当前元素减前一个元素大于2说明中间缺了多个数。但题目明确说只缺了一个数所以这种情况不会出现。不过为了代码健壮性可以只记录第一个缺失值。int repeat -1, missing -1; for (int i 1; i cnt; i) { if (data[i] data[i-1]) { repeat data[i]; } else if (data[i] - data[i-1] 2) { missing data[i-1] 1; } } printf(%d %d\n, repeat, missing);这段代码简洁明了但有一个边界情况要注意如果重复的数字和缺失的数字恰好位于序列的两端比如缺失的是最小值减一或者最大值加一那么遍历相邻元素是找不到的。但题目说编号是连续的正整数从某个最小值开始到某个最大值结束缺失的编号一定在最小值到最大值之间不会超出这个范围。所以相邻比较是安全的。4.3 排序方案的性能与边界测试qsort的平均时间复杂度是O(n log n)对于十万级别的数据运行时间在几十毫秒以内完全不会超时。空间上只需要一个数组没有额外开销。边界测试我建议至少覆盖这几种情况重复和缺失相邻比如1 2 3 3 5重复3缺失4。重复和缺失分离比如1 1 3 4 5重复1缺失2。重复在末尾缺失在开头比如2 3 4 5 5重复5缺失1。只有两个数比如1 1重复1缺失2。这种情况比较特殊因为序列只有两个元素缺失的是最大值加一。最后一种情况需要特别注意。如果输入只有两个相同的数排序后是1 1遍历时发现重复1但缺失的2不会通过相邻比较发现因为2不在数组里。这时候需要额外判断如果缺失值没找到那它可能是最大值加一。但题目说编号是连续的如果只有两个数且重复那缺失的只能是最大值加一。所以可以在遍历后加一个判断如果missing还是-1就取data[cnt-1] 1。不过更稳妥的做法是先找出数组中的最大值和最小值然后缺失值一定在min到max之间。如果遍历没找到再检查min - 1和max 1。但根据题目描述缺失值一定在范围内所以不用过度设计。5. 标记数组方案完整实现与对比5.1 标记数组的构建与使用标记数组方案的核心是先找出所有编号的最小值和最大值然后开一个大小为max - min 1的数组初始化为0。遍历所有编号把data[i] - min位置加一。最后遍历标记数组值为0的下标加min就是缺失编号值为2的下标加min就是重复编号。int min data[0], max data[0]; for (int i 1; i cnt; i) { if (data[i] min) min data[i]; if (data[i] max) max data[i]; } int range max - min 1; int *flag (int *)calloc(range, sizeof(int)); for (int i 0; i cnt; i) { flag[data[i] - min]; } int repeat -1, missing -1; for (int i 0; i range; i) { if (flag[i] 0) missing i min; if (flag[i] 2) repeat i min; } printf(%d %d\n, repeat, missing); free(flag);这段代码比排序方案更短而且不需要写比较函数。calloc会自动把数组清零省去了手动初始化的步骤。5.2 两种方案的实际运行对比我拿一组随机生成的十万个编号分别跑了两种方案。排序方案用qsort标记数组方案用calloc加遍历。结果如下方案数据量运行时间内存占用qsort排序100000约35ms约400KB标记数组100000约8ms约400KB range大小标记数组在时间上明显更快因为它是线性遍历没有排序的比较开销。内存方面如果编号范围是1到100000标记数组额外占用400KB左右完全可以接受。但如果编号范围是1到10000000标记数组就要占用40MB虽然现代机器扛得住但在一些内存受限的环境下就要谨慎。从比赛策略来说如果题目没有明确说编号范围很大我倾向于用标记数组因为代码短、跑得快、不容易出错。如果担心范围问题可以在读入数据后先判断max - min的大小如果超过某个阈值就改用排序。但这样代码就复杂了不如直接排序来得省心。5.3 标记数组方案的一个隐藏陷阱标记数组方案有一个容易被忽略的问题如果编号的最小值不是1比如从100开始那么flag数组的下标0对应的是100不是0。这个偏移量min必须在最后输出时加回去否则输出的编号全是错的。我见过有人写代码时忘了加min结果输出的重复和缺失编号都是小数字跟实际完全对不上。这个错误在调试时很容易发现但在比赛紧张的环境下如果没检查输出就可能白白丢分。另外如果编号范围很大但实际数据很稀疏比如只有100个编号但最大值是1000000标记数组会浪费大量空间。这种情况下排序方案更合适。所以选择方案前最好先扫一眼数据对范围有个大致判断。6. 常见问题与排查技巧实录6.1 输出顺序搞反了题目要求先输出重复编号再输出缺失编号。我见过有人先输出缺失再输出重复结果答案完全反了。这个错误很低级但在紧张环境下确实会发生。建议在代码里把变量命名清楚比如repeat和missing输出时按顺序写不要凭记忆。6.2 数组开太小导致越界如果编号数量超过数组容量程序会崩溃或者产生不可预期的结果。蓝桥杯的测试数据通常不会超过十万但如果你不确定可以把数组开到1000005。多占几MB内存换来的是安全。提示在C语言里数组越界不一定会立刻报错可能只是悄悄覆盖了其他变量的值导致结果莫名其妙。所以宁可开大一点不要卡着边界开。6.3 读入时漏掉最后一个数前面提到过如果文件末尾没有换行符逐字符读取的循环结束时最后一个数还没存入。这个问题的表现是缺失编号判断错误因为少了一个数可能导致缺失值变成最大值加一。解决方法是在循环外补一次判断。6.4 重复编号和缺失编号的判断条件写错排序方案里判断缺失的条件是data[i] - data[i-1] 2不是 2。虽然题目说只缺一个数但如果你写成 2逻辑上也没错只是不够精确。判断重复的条件是data[i] data[i-1]这个没问题。标记数组方案里判断缺失是flag[i] 0判断重复是flag[i] 2。注意不要写成flag[i] 1来判断重复因为如果某个编号出现了三次 1也会触发但题目说只重复一次所以 2更准确。6.5 常见问题速查表问题现象可能原因解决方法输出全是0标记数组没加min偏移输出时加上min缺失编号是最大值加一最后一个数没读入循环外补一次存入程序崩溃数组开太小增大数组容量重复和缺失输出反了输出顺序写错先repeat后missing缺失编号找不到遍历条件写错检查差值是否为2重复编号找不到比较条件写错检查是否相等6.6 一个实用的调试技巧如果你不确定读入是否正确可以在读入完成后先把所有编号打印出来看看数量和内容对不对。虽然比赛时不能提交调试代码但在本地测试时这个方法是最高效的。另外可以手动构造几组小数据比如1 2 3 3 5预期输出3 4跑一遍看看结果对不对。7. 从这道题延伸出的通用能力这道题表面上是找重复和缺失实际上训练的是几种很通用的能力。第一种是不定长数据的读入与解析这在很多题目里都会遇到比如读入一行字符串、读入矩阵、读入多组测试数据。掌握逐字符解析的方法以后遇到类似输入格式就不会慌。第二种是用空间换时间的权衡。排序方案和标记数组方案代表了两种不同的取舍排序省空间但费时间标记数组省时间但费空间。在实际开发中这种权衡无处不在。理解两种方案的适用场景比记住某一种写法更重要。第三种是边界条件的敏感度。这道题的边界情况包括只有两个数、重复和缺失相邻、缺失在两端、文件末尾无换行。这些情况在正常数据里可能不会出现但测试数据往往会故意覆盖。养成主动思考边界的习惯能帮你避开很多隐藏的坑。第四种是代码的健壮性。比如标记数组方案里如果max - min很大calloc可能返回NULL。虽然比赛时通常不会遇到但加上一个简单的判空检查代码就更可靠。这种习惯在写生产代码时尤其重要。8. 我的实操心得与最后建议这道题我前前后后写过好几遍每次都有新的体会。最开始我用的是排序方案因为思路最自然。后来发现标记数组更短更快就换成了标记数组。再后来遇到一道类似的题编号范围到了十亿级别标记数组直接爆内存只好又回到排序。所以我的建议是两种方案都要会根据题目条件灵活选择。如果让我给正在准备蓝桥杯的朋友一个建议那就是先把输入读入写对再考虑算法。我见过太多人算法思路没问题但读入写错导致结果全错。逐字符解析的方法虽然看起来笨但它是万能的不管输入格式怎么变都能正确读出所有数字。另外写完代码后一定要用几组边界数据测试。不要只跑题目给的样例样例往往太简单覆盖不到边界情况。自己构造几组极端数据比如只有一个数、所有数都相同、缺失在开头、缺失在末尾跑一遍看看结果对不对。这个习惯能帮你在比赛中多拿不少分。最后说一个我踩过的坑有一次我用标记数组方案编号范围是1到100000我开了100005的数组结果测试数据里有一个编号是100001直接越界了。从那以后我开数组都会多留一些余量或者先读入数据找出最大值再动态分配。这个教训让我明白永远不要假设数据不会超出你的预期。
阅读完成 · 觉得有帮助？
