先说一个我在PTA上常见的现象10分的题看起来简单但实验7-1-7 查找整数 这道题每年都能让一批刚学C语言的同学卡上好几个小时。我见过太多类似的情况本地编译运行一切正常一提交就是答案错误问了一圈发现是位置编号从0开始输出而不是从1开始。这道题虽然分值不大但它是顺序查找、数组遍历、条件输出这几个基本功的集合作业也是后续二分查找查找第k个满足条件的数等进阶题目的地基。这篇文章我会把题目背后的考点、读题时容易忽略的信息、三种不同风格的写法、PTA判题时常见的坑以及怎么把这道10分题的价值榨干一次性讲透。不管是刚开始学数组的大一新生还是已经刷到函数题、想回来补基础的同学都可以对照着看。1. 题目到底在考什么10分背后的三个基本功很多同学拿到这道题的第一反应是就这然后十分钟写完提交。但据我观察一遍过的人其实没有想象中那么多。这道题表面是找一个数实际上是在考察三个基础能力数组的声明与遍历、用循环配合条件判断实现查找逻辑、以及严格遵循题目要求的输入输出格式。任何一个环节出了问题PTA都会毫不留情地给你一个红叉。1.1 数组把一堆数装进同一个变量名里题目要求从输入的N个整数中查找给定的X这意味着你面对的是一组同类型的数据而不是一个单独的数。在C语言里处理一组同类型数据的最自然方案就是数组。int a[20];这一行声明了20个int类型的变量它们通过下标访问a[0]、a[1]一直到a[19]。数组最大的好处是能用循环遍历比如把n个数读进来for (i 0; i n; i) { scanf(%d, a[i]); }这里有一个初学者很容易绕不过来的点为什么不用20个独立的变量比如int a1, a2, a3, ...这样写原因很简单变量的个数是题目运行时才能确定的第一行的n你不能预先写好n个scanf。而且就算你写死20个变量要逐个比较也是一件极其痛苦的事。数组的意义就在于用下标把第几个和值是多少绑定让循环可以统一处理。1.2 顺序查找最朴素也最通用的查找方式查找一个数在数组里的位置最直接的做法就是从第一个元素开始一个一个比直到找到目标或者把所有元素都比完。这个思路就是顺序查找也叫线性查找时间复杂度是O(n)。顺序查找虽然听起来笨但它是理解后续所有查找算法的基础。二分查找要求数据有序哈希查找要求设计哈希函数而顺序查找什么都不要求——哪怕数据是无序的、有重复的它都能工作。这道题用顺序查找不是因为它简单而是因为它是在数组中做操作最典型的开端。1.3 输入输出的隐形扣分点PTA判题是严格比对输出字符的多一个空格、少一个换行、大小写不一致都算错误。这道题输出要么是位置编号换行要么是Not Found换行。这里我特别强调一下Not Found的格式N是大写F是大写其余是小写中间一个空格后面没有句号。我见过不少同学写成Not foundNOT FOUNDNot Found.的这些全部会判错。有时候你代码逻辑完全没问题就是格式细节不对这种错误最冤。所以拿到任何PTA题目第一步不是写代码而是把输出说明看三遍。2. 拿到题目先别急着写代码把题干拆成这几条写程序之前先把题目里的每个条件都翻译成代码层面的约束。我习惯用笔在草稿纸上把输入格式、输出格式、特殊要求列成三条然后再动手。这道题的题干虽然短但信息密度不小。2.1 输入格式里藏着哪些信息题目输入分两行第一行给出两个正整数N和X第二行给出N个整数。N是要输入的整数个数这道题通常限制为N≤20。这个限制意味着你可以放心地用固定大小数组int a[20]而不用担心越界。X是要查找的目标。第二行的N个整数用空格分隔你需要用循环把它们逐一读入。有一个细节值得注意题目说N是正整数但如果你提交的测试点里出现了读入失败的情况多半是输入格式没对上。另外C语言里scanf(%d %d, n, x)会自动跳过空白字符空格、换行、制表符所以第一行的换行并不影响第二行的读入。2.2 第一次出现的位置为什么是题眼这是整道题最容易被忽略的地方。题干说的是如果找到输出X在数列中第一次出现的位置关键词有两个第一次和位置。第一次意味着输入数据里可能有重复数字。比如输入2 4 2 8查找2正确输出是1而不是3。如果你在循环里把所有匹配的位置都记录下来最后不小心输出了最后一次匹配的位置就会答案错误。位置意味着编号从1开始。这个和数组下标从0开始的规则不一致。你找到的是下标i但输出时要输出i1。我见过太多同学调试的时候发现明明找到了输出却是0就是因为少了这个映射。建议在写输出语句时直接写成printf(%d\n, i 1);而不是先算一个位置变量再输出减少一步出错的机会。2.3 输出格式大小写和换行一个都不能错输出没有找到时要输出Not Found注意三点一是大小写二是中间这个空格三是末尾的换行。用printf输出时直接写Not Found\n不要拼写、不要加标点。另外找到时输出的位置之后也要换行。PTA的判题脚本对换行敏感但通常不会因为最后一行缺少换行就判错不过我建议还是规规矩矩加\n养成习惯对后续题目有好处。3. 代码实现从最朴素的写法到能加分的写法这一章我给出三种思路的完整代码每一种都会逐行解释。你可以根据自己的水平选择如果是初学者老老实实写第一种如果已经理解数组和循环可以试试第二种如果想把基础打得更扎实建议把第三种封装函数的写法也掌握。3.1 基础版开了数组用flag标记结果#include stdio.h int main() { int n, x; scanf(%d %d, n, x); int a[20]; int i; for (i 0; i n; i) { scanf(%d, a[i]); } int flag 0; for (i 0; i n; i) { if (a[i] x) { printf(%d\n, i 1); flag 1; break; } } if (flag 0) { printf(Not Found\n); } return 0; }这段代码的思路是先用两个循环完成读入所有整数和逐个查找目标两个阶段再用一个flag变量记录是否找到。为什么需要flag因为第二个for循环有两个出口一是break跳出来的找到了二是i循环到n正常结束的没找到。循环结束后程序无法区分自己是从哪个出口出来的所以要借助flag。一旦找到先输出位置把flag置1然后break跳出循环如果循环正常结束说明全程没有匹配flag保持0执行Not Found输出。这里有个小细节找到后立即break是因为题目只要第一次出现的位置。如果你不break后面即使找到了也不会有更新的输出但在效率上是浪费的。更重要的是不break的话循环会继续跑如果后面还有匹配项你的flag可能被反复置1虽然结果可能还是对的但代码逻辑就不干净了。3.2 优化版边读边找连数组都不用开#include stdio.h int main() { int n, x; scanf(%d %d, n, x); int num; int i; for (i 1; i n; i) { scanf(%d, num); if (num x) { printf(%d\n, i); return 0; } } printf(Not Found\n); return 0; }这个版本更巧妙因为题目只要求输出第一次出现的位置所以你没有必要把读入的所有数都存下来再回头找。你可以一边读一边比较读到第几个数的时候就检查它是不是目标是的话立刻输出并结束程序。注意这里的循环变量i是从1开始的正好对应位置编号。读入scanf(%d, num)如果num x直接printf(%d\n, i)然后return 0结束整个main函数后面的Not Found自然就不会执行。如果循环正常结束说明从头到尾没有匹配过这时再用printf输出Not Found。这种边读边处理的思路在处理流式数据时非常有用也是后续学习文件读写时的一个重要思维。不过我要提醒一句如果题目要求输出X出现的所有位置或者输出最后一次出现的位置这个边读边处理的方案就不够了你得老老实实存数组。所以不要觉得这个版本最优就只背它两种写法都需要理解。3.3 函数封装为后续进阶题目做准备#include stdio.h int search(int a[], int n, int x) { int i; for (i 0; i n; i) { if (a[i] x) { return i 1; } } return -1; } int main() { int n, x; scanf(%d %d, n, x); int a[20]; int i; for (i 0; i n; i) { scanf(%d, a[i]); } int pos search(a, n, x); if (pos -1) { printf(Not Found\n); } else { printf(%d\n, pos); } return 0; }第三种写法把查找逻辑单独封装成了函数search。函数接收三个参数数组a、长度n、目标x返回值是找到时的位置从1开始或-1未找到.为什么用-1作为失败标记因为题目里的位置是正整数-1不可能出现在合法输出中所以可以安全地充当异常/未找到信号。main函数里只需要判断返回值即可。这种封装的价值在后续PTA的函数题中会体现得非常明显。比如二分查找PTA函数这类题目题目会直接给你一个函数接口让你实现你的查找逻辑就写在那个实现里。提前养成把具体算法封装成函数的习惯后面做函数题会轻松很多。3.4 复杂度分析这个答案为什么是对的还是有必要把复杂度说清楚PTA虽然不考复杂度分析但后续课程和面试会考。时间最坏情况下把n个数全部比较一遍时间复杂度O(n)平均情况是O(n/2)依然记作O(n)。空间如果用数组存储空间复杂度O(n)如果用边读边找的版本除了一些变量外不占用额外空间空间复杂度O(1)。对于N≤20的数据规模即使是最差的O(n)方案也绰绰有余。这也是PTA上一个有趣的地方数据规模往往决定了算法选择的自由度。如果N变成10的7次方顺序查找就不一定能过了那时候才需要二分查找、哈希表这些更高效的手段。4. 常见错误与排查技巧PTA判题到底在judge什么我在帮同学看代码的时候发现这道题的报错场景高度集中。这里我把高频错误整理成速查表然后再展开讲几个典型的翻车现场。4.1 高频错误对照速查表错误现象可能原因解决方法答案错误始终输出0输出的是数组下标i不是位置i1输出时改为i1答案错误重复数字时输出位置靠后记录所有匹配位置最后输出了最后一个找到第一个匹配就break或return答案错误没有找到时输出乱码未初始化flag变量未找到时flag值不确定定义flag时初始化为0格式错误Not Found不对大小写错误、单词拼错、加了标点严格按Not Found输出答案错误输出位置全部偏移一位循环从i1开始但数组访问使用a[i]区分位置编号和数组下标编译错误数组大小不对用了int a[n]但编译环境不支持变长数组用int a[20]或int a[100]段错误/运行时错误循环条件in导致访问a[n]越界循环条件改为in4.2 一个典型的翻车现场输出下标还是位置我印象最深的是一个学弟的代码逻辑完全正确就是输出那行写了printf(%d\n, i)。他本地测试了好几组数据查找1数组是2 3 1 4他惊人有输出的编号少了1。他问我为什么我说你把数组下标当位置输出了。改成i1一次过。这种错误调试起来很难发现因为大部分时候找到的数在数组中间你光看输出2可能觉得就是第二个位置实际它代表的是下标2、位置3语义已经完全偏了。我的建议是写输出语句之前先在心里问自己一句当前变量到底代表下标还是位置这道题以及后续很多数组题目都会频繁出现这种下标从0、编号从1的映射问题。4.3 本地正确、提交报错可能是这些原因本地运行是对的一提交就红是PTA新手最崩溃的情景。结合这道题常见原因有三个。第一你的本地测试用例太弱。比如你只测试了找到且目标在第一个位置的情况恰好输出数组下标和位置都是1看起来对了但一换测试数据就露馅。建议至少覆盖目标在中间、目标在末尾、目标不存在、目标重复出现这四种情况。第二数组越界导致的未定义行为。举个常见例子循环写成for(i 0; i n; i)在本地可能因为内存布局运气好没崩但PTA的数据集一旦让越界访问触及不该碰的内存就会段错误。这点一定要小心数组访问范围是[0, n-1]不是[0, n]。第三输入数据没有读完。有人会在循环里遇到目标后直接return但此时如果还有剩余输入没读理论上不算问题。可如果你用了某些特殊写法比如先scanf了一部分然后没有继续读入而程序又依赖后面某个变量来判断流程那就会出问题。最简单的对策严格按照读入全部数据 - 查找 - 输出的顺序来写。4.4 设计测试用例的方法这里分享一个我验证数组类题目时固定使用的测试用例矩阵。不需要多复杂但一定要覆盖边界和重复场景。用例1n1x等于唯一的那个数预期输出1。用例2n5x不存在预期输出Not Found。用例3目标在第一个位置验证位置编号是否从1开始。用例4目标在最后一个位置验证循环边界是否正确。用例5输入含负数验证scanf的%d能正常读负号。用例6重复数字目标出现多次预期输出第一次的位置。把这六个用例如法炮制一遍代码的可靠性会大幅提升。养成这种测试习惯比多背十道题都有用。5. 从查找整数出发算法学习的一个小节点这道题做完之后不要急着关掉页面。你刚掌握的在数组里找东西这个能力会在一系列后续题目中不断变形出现。提前了解一下这些变体后面刷题会顺很多。5.1 顺序查找之后下一步学什么顺序查找是无脑遍历但它的天花板很低数据一大就慢。接下来在PTA和数据结构课程里你会陆续遇到两类查找问题。第一类是有序数组的查找代表就是二分查找。二分查找每次把查找区间折半时间复杂度是O(log n)但前提是数组已经有序。PTA上经典的二分查找PTA函数题要求你实现一个函数接口在有序数组里查找目标并返回位置。如果你能先把这道查找整数的顺序查找思路写熟再对比二分查找的每次砍一半理解起来会快很多。第二类是字符串里的查找比如在字符串中逆序输出、模式匹配等。原理上依然是顺序查找的变体把字符数组里的每个元素和目标去比较。不同的是字符串多了\0结尾的判断遍历条件和整数数组略有差别。5.2 哪些题目和这道题是同类项在你接下来刷PTA的过程中很多题都会用到这里面的核心能力找最大值和最小值同样是遍历数组只是比较条件从等于target变成比当前最值大/小。统计某个数出现的次数把break去掉每次匹配就count最后输出count。找出数组中所有和目标相等的数找到就输出而不是找到就返回。数组逆序输出核心也是数组遍历只是从最后一个下标往0循环。去重遍历数组检查当前元素是否在之前出现过——又是一个查找。你会发现几乎所有数组类题目都离不开顺序查找这个底层思想。把这道题吃透等于给自己打下了数组操作的基本盘。5.3 一个值得养成的代码习惯借着这道题我想分享一个实际写代码时非常受益的习惯先画循环不变式再写循环。听起来很高大上其实就是写循环前先明确一件事——这个循环结束时哪些变量应该处于什么状态。以这道题的第二个for循环为例循环结束时有且仅有两种情况情况一break跳出此时flag1i是目标所在的下标情况二in正常结束此时flag0代表没有找到。知道了这两种结束状态你就知道为什么需要flag以及为什么break后不应该再执行Not Found输出。很多同学的bug本质上就是没想清楚循环结束后的状态。把这个习惯带到后续所有循环题目里能省掉大量调试时间。最后说点个人的体会。我刷题这些年遇到的最多的不是不会写而是差不多就行了的心态。像查找整数这种10分题写完提交通过后就再也不看一眼实际上很浪费——它包含的数组遍历、flag标记、边界处理和测试用例设计是以后上百道题都会反复用到的基础能力。每次做完一道题多花十分钟做三件事重新读一遍自己的代码、跑一遍边界测试用例、想一想如果数据规模放大一百倍该怎么改。坚持下去你对算法和数据结构的理解会明显比同龄人深一截。