先說一個我在PTA上常見的現(xiàn)象10分的題看起來簡單但實(shí)驗(yàn)7-1-7 查找整數(shù) 這道題每年都能讓一批剛學(xué)C語言的同學(xué)卡上好幾個小時。我見過太多類似的情況本地編譯運(yùn)行一切正常一提交就是答案錯誤問了一圈發(fā)現(xiàn)是位置編號從0開始輸出而不是從1開始。這道題雖然分值不大但它是順序查找、數(shù)組遍歷、條件輸出這幾個基本功的集合作業(yè)也是后續(xù)二分查找查找第k個滿足條件的數(shù)等進(jìn)階題目的地基。這篇文章我會把題目背后的考點(diǎn)、讀題時容易忽略的信息、三種不同風(fēng)格的寫法、PTA判題時常見的坑以及怎么把這道10分題的價值榨干一次性講透。不管是剛開始學(xué)數(shù)組的大一新生還是已經(jīng)刷到函數(shù)題、想回來補(bǔ)基礎(chǔ)的同學(xué)都可以對照著看。1. 題目到底在考什么10分背后的三個基本功很多同學(xué)拿到這道題的第一反應(yīng)是就這然后十分鐘寫完提交。但據(jù)我觀察一遍過的人其實(shí)沒有想象中那么多。這道題表面是找一個數(shù)實(shí)際上是在考察三個基礎(chǔ)能力數(shù)組的聲明與遍歷、用循環(huán)配合條件判斷實(shí)現(xiàn)查找邏輯、以及嚴(yán)格遵循題目要求的輸入輸出格式。任何一個環(huán)節(jié)出了問題PTA都會毫不留情地給你一個紅叉。1.1 數(shù)組把一堆數(shù)裝進(jìn)同一個變量名里題目要求從輸入的N個整數(shù)中查找給定的X這意味著你面對的是一組同類型的數(shù)據(jù)而不是一個單獨(dú)的數(shù)。在C語言里處理一組同類型數(shù)據(jù)的最自然方案就是數(shù)組。int a[20];這一行聲明了20個int類型的變量它們通過下標(biāo)訪問a[0]、a[1]一直到a[19]。數(shù)組最大的好處是能用循環(huán)遍歷比如把n個數(shù)讀進(jìn)來for (i 0; i n; i) { scanf(%d, a[i]); }這里有一個初學(xué)者很容易繞不過來的點(diǎn)為什么不用20個獨(dú)立的變量比如int a1, a2, a3, ...這樣寫原因很簡單變量的個數(shù)是題目運(yùn)行時才能確定的第一行的n你不能預(yù)先寫好n個scanf。而且就算你寫死20個變量要逐個比較也是一件極其痛苦的事。數(shù)組的意義就在于用下標(biāo)把第幾個和值是多少綁定讓循環(huán)可以統(tǒng)一處理。1.2 順序查找最樸素也最通用的查找方式查找一個數(shù)在數(shù)組里的位置最直接的做法就是從第一個元素開始一個一個比直到找到目標(biāo)或者把所有元素都比完。這個思路就是順序查找也叫線性查找時間復(fù)雜度是O(n)。順序查找雖然聽起來笨但它是理解后續(xù)所有查找算法的基礎(chǔ)。二分查找要求數(shù)據(jù)有序哈希查找要求設(shè)計哈希函數(shù)而順序查找什么都不要求——哪怕數(shù)據(jù)是無序的、有重復(fù)的它都能工作。這道題用順序查找不是因?yàn)樗唵味且驗(yàn)樗窃跀?shù)組中做操作最典型的開端。1.3 輸入輸出的隱形扣分點(diǎn)PTA判題是嚴(yán)格比對輸出字符的多一個空格、少一個換行、大小寫不一致都算錯誤。這道題輸出要么是位置編號換行要么是Not Found換行。這里我特別強(qiáng)調(diào)一下Not Found的格式N是大寫F是大寫其余是小寫中間一個空格后面沒有句號。我見過不少同學(xué)寫成Not foundNOT FOUNDNot Found.的這些全部會判錯。有時候你代碼邏輯完全沒問題就是格式細(xì)節(jié)不對這種錯誤最冤。所以拿到任何PTA題目第一步不是寫代碼而是把輸出說明看三遍。2. 拿到題目先別急著寫代碼把題干拆成這幾條寫程序之前先把題目里的每個條件都翻譯成代碼層面的約束。我習(xí)慣用筆在草稿紙上把輸入格式、輸出格式、特殊要求列成三條然后再動手。這道題的題干雖然短但信息密度不小。2.1 輸入格式里藏著哪些信息題目輸入分兩行第一行給出兩個正整數(shù)N和X第二行給出N個整數(shù)。N是要輸入的整數(shù)個數(shù)這道題通常限制為N≤20。這個限制意味著你可以放心地用固定大小數(shù)組int a[20]而不用擔(dān)心越界。X是要查找的目標(biāo)。第二行的N個整數(shù)用空格分隔你需要用循環(huán)把它們逐一讀入。有一個細(xì)節(jié)值得注意題目說N是正整數(shù)但如果你提交的測試點(diǎn)里出現(xiàn)了讀入失敗的情況多半是輸入格式?jīng)]對上。另外C語言里scanf(%d %d, n, x)會自動跳過空白字符空格、換行、制表符所以第一行的換行并不影響第二行的讀入。2.2 第一次出現(xiàn)的位置為什么是題眼這是整道題最容易被忽略的地方。題干說的是如果找到輸出X在數(shù)列中第一次出現(xiàn)的位置關(guān)鍵詞有兩個第一次和位置。第一次意味著輸入數(shù)據(jù)里可能有重復(fù)數(shù)字。比如輸入2 4 2 8查找2正確輸出是1而不是3。如果你在循環(huán)里把所有匹配的位置都記錄下來最后不小心輸出了最后一次匹配的位置就會答案錯誤。位置意味著編號從1開始。這個和數(shù)組下標(biāo)從0開始的規(guī)則不一致。你找到的是下標(biāo)i但輸出時要輸出i1。我見過太多同學(xué)調(diào)試的時候發(fā)現(xiàn)明明找到了輸出卻是0就是因?yàn)樯倭诉@個映射。建議在寫輸出語句時直接寫成printf(%d\n, i 1);而不是先算一個位置變量再輸出減少一步出錯的機(jī)會。2.3 輸出格式大小寫和換行一個都不能錯輸出沒有找到時要輸出Not Found注意三點(diǎn)一是大小寫二是中間這個空格三是末尾的換行。用printf輸出時直接寫Not Found\n不要拼寫、不要加標(biāo)點(diǎn)。另外找到時輸出的位置之后也要換行。PTA的判題腳本對換行敏感但通常不會因?yàn)樽詈笠恍腥鄙贀Q行就判錯不過我建議還是規(guī)規(guī)矩矩加\n養(yǎng)成習(xí)慣對后續(xù)題目有好處。3. 代碼實(shí)現(xiàn)從最樸素的寫法到能加分的寫法這一章我給出三種思路的完整代碼每一種都會逐行解釋。你可以根據(jù)自己的水平選擇如果是初學(xué)者老老實(shí)實(shí)寫第一種如果已經(jīng)理解數(shù)組和循環(huán)可以試試第二種如果想把基礎(chǔ)打得更扎實(shí)建議把第三種封裝函數(shù)的寫法也掌握。3.1 基礎(chǔ)版開了數(shù)組用flag標(biāo)記結(jié)果#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; }這段代碼的思路是先用兩個循環(huán)完成讀入所有整數(shù)和逐個查找目標(biāo)兩個階段再用一個flag變量記錄是否找到。為什么需要flag因?yàn)榈诙€for循環(huán)有兩個出口一是break跳出來的找到了二是i循環(huán)到n正常結(jié)束的沒找到。循環(huán)結(jié)束后程序無法區(qū)分自己是從哪個出口出來的所以要借助flag。一旦找到先輸出位置把flag置1然后break跳出循環(huán)如果循環(huán)正常結(jié)束說明全程沒有匹配flag保持0執(zhí)行Not Found輸出。這里有個小細(xì)節(jié)找到后立即break是因?yàn)轭}目只要第一次出現(xiàn)的位置。如果你不break后面即使找到了也不會有更新的輸出但在效率上是浪費(fèi)的。更重要的是不break的話循環(huán)會繼續(xù)跑如果后面還有匹配項你的flag可能被反復(fù)置1雖然結(jié)果可能還是對的但代碼邏輯就不干凈了。3.2 優(yōu)化版邊讀邊找連數(shù)組都不用開#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; }這個版本更巧妙因?yàn)轭}目只要求輸出第一次出現(xiàn)的位置所以你沒有必要把讀入的所有數(shù)都存下來再回頭找。你可以一邊讀一邊比較讀到第幾個數(shù)的時候就檢查它是不是目標(biāo)是的話立刻輸出并結(jié)束程序。注意這里的循環(huán)變量i是從1開始的正好對應(yīng)位置編號。讀入scanf(%d, num)如果num x直接printf(%d\n, i)然后return 0結(jié)束整個main函數(shù)后面的Not Found自然就不會執(zhí)行。如果循環(huán)正常結(jié)束說明從頭到尾沒有匹配過這時再用printf輸出Not Found。這種邊讀邊處理的思路在處理流式數(shù)據(jù)時非常有用也是后續(xù)學(xué)習(xí)文件讀寫時的一個重要思維。不過我要提醒一句如果題目要求輸出X出現(xiàn)的所有位置或者輸出最后一次出現(xiàn)的位置這個邊讀邊處理的方案就不夠了你得老老實(shí)實(shí)存數(shù)組。所以不要覺得這個版本最優(yōu)就只背它兩種寫法都需要理解。3.3 函數(shù)封裝為后續(xù)進(jìn)階題目做準(zhǔn)備#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; }第三種寫法把查找邏輯單獨(dú)封裝成了函數(shù)search。函數(shù)接收三個參數(shù)數(shù)組a、長度n、目標(biāo)x返回值是找到時的位置從1開始或-1未找到.為什么用-1作為失敗標(biāo)記因?yàn)轭}目里的位置是正整數(shù)-1不可能出現(xiàn)在合法輸出中所以可以安全地充當(dāng)異常/未找到信號。main函數(shù)里只需要判斷返回值即可。這種封裝的價值在后續(xù)PTA的函數(shù)題中會體現(xiàn)得非常明顯。比如二分查找PTA函數(shù)這類題目題目會直接給你一個函數(shù)接口讓你實(shí)現(xiàn)你的查找邏輯就寫在那個實(shí)現(xiàn)里。提前養(yǎng)成把具體算法封裝成函數(shù)的習(xí)慣后面做函數(shù)題會輕松很多。3.4 復(fù)雜度分析這個答案為什么是對的還是有必要把復(fù)雜度說清楚PTA雖然不考復(fù)雜度分析但后續(xù)課程和面試會考。時間最壞情況下把n個數(shù)全部比較一遍時間復(fù)雜度O(n)平均情況是O(n/2)依然記作O(n)。空間如果用數(shù)組存儲空間復(fù)雜度O(n)如果用邊讀邊找的版本除了一些變量外不占用額外空間空間復(fù)雜度O(1)。對于N≤20的數(shù)據(jù)規(guī)模即使是最差的O(n)方案也綽綽有余。這也是PTA上一個有趣的地方數(shù)據(jù)規(guī)模往往決定了算法選擇的自由度。如果N變成10的7次方順序查找就不一定能過了那時候才需要二分查找、哈希表這些更高效的手段。4. 常見錯誤與排查技巧PTA判題到底在judge什么我在幫同學(xué)看代碼的時候發(fā)現(xiàn)這道題的報錯場景高度集中。這里我把高頻錯誤整理成速查表然后再展開講幾個典型的翻車現(xiàn)場。4.1 高頻錯誤對照速查表錯誤現(xiàn)象可能原因解決方法答案錯誤始終輸出0輸出的是數(shù)組下標(biāo)i不是位置i1輸出時改為i1答案錯誤重復(fù)數(shù)字時輸出位置靠后記錄所有匹配位置最后輸出了最后一個找到第一個匹配就break或return答案錯誤沒有找到時輸出亂碼未初始化flag變量未找到時flag值不確定定義flag時初始化為0格式錯誤Not Found不對大小寫錯誤、單詞拼錯、加了標(biāo)點(diǎn)嚴(yán)格按Not Found輸出答案錯誤輸出位置全部偏移一位循環(huán)從i1開始但數(shù)組訪問使用a[i]區(qū)分位置編號和數(shù)組下標(biāo)編譯錯誤數(shù)組大小不對用了int a[n]但編譯環(huán)境不支持變長數(shù)組用int a[20]或int a[100]段錯誤/運(yùn)行時錯誤循環(huán)條件in導(dǎo)致訪問a[n]越界循環(huán)條件改為in4.2 一個典型的翻車現(xiàn)場輸出下標(biāo)還是位置我印象最深的是一個學(xué)弟的代碼邏輯完全正確就是輸出那行寫了printf(%d\n, i)。他本地測試了好幾組數(shù)據(jù)查找1數(shù)組是2 3 1 4他驚人有輸出的編號少了1。他問我為什么我說你把數(shù)組下標(biāo)當(dāng)位置輸出了。改成i1一次過。這種錯誤調(diào)試起來很難發(fā)現(xiàn)因?yàn)榇蟛糠謺r候找到的數(shù)在數(shù)組中間你光看輸出2可能覺得就是第二個位置實(shí)際它代表的是下標(biāo)2、位置3語義已經(jīng)完全偏了。我的建議是寫輸出語句之前先在心里問自己一句當(dāng)前變量到底代表下標(biāo)還是位置這道題以及后續(xù)很多數(shù)組題目都會頻繁出現(xiàn)這種下標(biāo)從0、編號從1的映射問題。4.3 本地正確、提交報錯可能是這些原因本地運(yùn)行是對的一提交就紅是PTA新手最崩潰的情景。結(jié)合這道題常見原因有三個。第一你的本地測試用例太弱。比如你只測試了找到且目標(biāo)在第一個位置的情況恰好輸出數(shù)組下標(biāo)和位置都是1看起來對了但一換測試數(shù)據(jù)就露餡。建議至少覆蓋目標(biāo)在中間、目標(biāo)在末尾、目標(biāo)不存在、目標(biāo)重復(fù)出現(xiàn)這四種情況。第二數(shù)組越界導(dǎo)致的未定義行為。舉個常見例子循環(huán)寫成for(i 0; i n; i)在本地可能因?yàn)閮?nèi)存布局運(yùn)氣好沒崩但PTA的數(shù)據(jù)集一旦讓越界訪問觸及不該碰的內(nèi)存就會段錯誤。這點(diǎn)一定要小心數(shù)組訪問范圍是[0, n-1]不是[0, n]。第三輸入數(shù)據(jù)沒有讀完。有人會在循環(huán)里遇到目標(biāo)后直接return但此時如果還有剩余輸入沒讀理論上不算問題?？扇绻阌昧四承┨厥鈱懛ū热缦萻canf了一部分然后沒有繼續(xù)讀入而程序又依賴后面某個變量來判斷流程那就會出問題。最簡單的對策嚴(yán)格按照讀入全部數(shù)據(jù) - 查找 - 輸出的順序來寫。4.4 設(shè)計測試用例的方法這里分享一個我驗(yàn)證數(shù)組類題目時固定使用的測試用例矩陣。不需要多復(fù)雜但一定要覆蓋邊界和重復(fù)場景。用例1n1x等于唯一的那個數(shù)預(yù)期輸出1。用例2n5x不存在預(yù)期輸出Not Found。用例3目標(biāo)在第一個位置驗(yàn)證位置編號是否從1開始。用例4目標(biāo)在最后一個位置驗(yàn)證循環(huán)邊界是否正確。用例5輸入含負(fù)數(shù)驗(yàn)證scanf的%d能正常讀負(fù)號。用例6重復(fù)數(shù)字目標(biāo)出現(xiàn)多次預(yù)期輸出第一次的位置。把這六個用例如法炮制一遍代碼的可靠性會大幅提升。養(yǎng)成這種測試習(xí)慣比多背十道題都有用。5. 從查找整數(shù)出發(fā)算法學(xué)習(xí)的一個小節(jié)點(diǎn)這道題做完之后不要急著關(guān)掉頁面。你剛掌握的在數(shù)組里找東西這個能力會在一系列后續(xù)題目中不斷變形出現(xiàn)。提前了解一下這些變體后面刷題會順很多。5.1 順序查找之后下一步學(xué)什么順序查找是無腦遍歷但它的天花板很低數(shù)據(jù)一大就慢。接下來在PTA和數(shù)據(jù)結(jié)構(gòu)課程里你會陸續(xù)遇到兩類查找問題。第一類是有序數(shù)組的查找代表就是二分查找。二分查找每次把查找區(qū)間折半時間復(fù)雜度是O(log n)但前提是數(shù)組已經(jīng)有序。PTA上經(jīng)典的二分查找PTA函數(shù)題要求你實(shí)現(xiàn)一個函數(shù)接口在有序數(shù)組里查找目標(biāo)并返回位置。如果你能先把這道查找整數(shù)的順序查找思路寫熟再對比二分查找的每次砍一半理解起來會快很多。第二類是字符串里的查找比如在字符串中逆序輸出、模式匹配等。原理上依然是順序查找的變體把字符數(shù)組里的每個元素和目標(biāo)去比較。不同的是字符串多了\0結(jié)尾的判斷遍歷條件和整數(shù)數(shù)組略有差別。5.2 哪些題目和這道題是同類項在你接下來刷PTA的過程中很多題都會用到這里面的核心能力找最大值和最小值同樣是遍歷數(shù)組只是比較條件從等于target變成比當(dāng)前最值大/小。統(tǒng)計某個數(shù)出現(xiàn)的次數(shù)把break去掉每次匹配就count最后輸出count。找出數(shù)組中所有和目標(biāo)相等的數(shù)找到就輸出而不是找到就返回。數(shù)組逆序輸出核心也是數(shù)組遍歷只是從最后一個下標(biāo)往0循環(huán)。去重遍歷數(shù)組檢查當(dāng)前元素是否在之前出現(xiàn)過——又是一個查找。你會發(fā)現(xiàn)幾乎所有數(shù)組類題目都離不開順序查找這個底層思想。把這道題吃透等于給自己打下了數(shù)組操作的基本盤。5.3 一個值得養(yǎng)成的代碼習(xí)慣借著這道題我想分享一個實(shí)際寫代碼時非常受益的習(xí)慣先畫循環(huán)不變式再寫循環(huán)。聽起來很高大上其實(shí)就是寫循環(huán)前先明確一件事——這個循環(huán)結(jié)束時哪些變量應(yīng)該處于什么狀態(tài)。以這道題的第二個for循環(huán)為例循環(huán)結(jié)束時有且僅有兩種情況情況一break跳出此時flag1i是目標(biāo)所在的下標(biāo)情況二in正常結(jié)束此時flag0代表沒有找到。知道了這兩種結(jié)束狀態(tài)你就知道為什么需要flag以及為什么break后不應(yīng)該再執(zhí)行Not Found輸出。很多同學(xué)的bug本質(zhì)上就是沒想清楚循環(huán)結(jié)束后的狀態(tài)。把這個習(xí)慣帶到后續(xù)所有循環(huán)題目里能省掉大量調(diào)試時間。最后說點(diǎn)個人的體會。我刷題這些年遇到的最多的不是不會寫而是差不多就行了的心態(tài)。像查找整數(shù)這種10分題寫完提交通過后就再也不看一眼實(shí)際上很浪費(fèi)——它包含的數(shù)組遍歷、flag標(biāo)記、邊界處理和測試用例設(shè)計是以后上百道題都會反復(fù)用到的基礎(chǔ)能力。每次做完一道題多花十分鐘做三件事重新讀一遍自己的代碼、跑一遍邊界測試用例、想一想如果數(shù)據(jù)規(guī)模放大一百倍該怎么改。堅持下去你對算法和數(shù)據(jù)結(jié)構(gòu)的理解會明顯比同齡人深一截。