#數組標記法在演算法題中的應用 什麼？！你還不知道數組在演算法題中不僅起儲存數據的作用，還可以起鏈接標記的作用？哈哈不要緊，原來我也是不知道的，我是看了我好哥們的做題思路才知道這個方法的。。。 我們先聲明一個長度為5數組arr[5]，再為arr[5]賦值arr[]={"q","w","e","r",“t ...
#數組標記法在演算法題中的應用 什麼？！你還不知道數組在演算法題中不僅起儲存數據的作用，還可以起鏈接標記的作用？哈哈不要緊，原來我也是不知道的，我是看了我好哥們的做題思路才知道這個方法的。。。 ---- 我們先聲明一個長度為5數組arr[5]，再為arr[5]賦值arr[]={"q","w","e","r",“t”}。這樣我們訪問arr[0]值為“q”，arr[1]值為w...你會發現通過數組arr[i]=某個字母，序號與字母形成了一種索引關係，即序號指向了數組中的某一個元素，這就好比Python中的字典，C++中的map，數組的序號可以看做是鍵（key），對應的元素就可以看做是值（value），這樣我們就可以解決很多問題，比如讓編譯器和我們都頭疼的數組（或字元串去重問題），PTA中有很多這樣的例題，下麵我們看一道。。。 --- 1093 字元串A+B （20 分) 給定兩個字元串 A 和 B，本題要求你輸出 A+B，即兩個字元串的並集。要求先輸出 A，再輸出 B，但重覆的字元必須被剔除。
輸入格式： 輸入在兩行中分別給出 A 和 B，均為長度不超過 10^6的、由可見 ASCII 字元 (即碼值為32~126)和空格組成的、由回車標識結束的非空字元串。
輸出格式： 在一行中輸出題面要求的 A 和 B 的和。
輸入樣例： This is a sample test to show you_How it works 輸出樣例： This ampletowyu_Hrk --- 字元串拼接可以說是基本操作，我們在這兒就不在贅述了（拼接後的的字元串我們聲明為a吧），我們主要談談如何實現字元串去重，常規方法，也是最容易想到的方法就是，設立兩層迴圈，複製a字元串（副本我們稱之為b吧）外層迴圈遍歷拼接後字元串的每個字母，內層迴圈用外層當前的字母i與副本b中的當前字元i以後的字元比較，如果在b中沒有找到與當前字元相同的字元，我們就輸出i；這樣做的時間複雜度為O（n^2）. 我們大可以換個思路。。。字元和是否重合的狀態其實是一個索引的關係，即每個字元對應了一種狀態（有或無），這樣我們就可以使用我們之間提到的數組來維持兩者的關係。當然你會說數組的序號是一個數字，怎麼能把字元當序號呢？答案是字元都對應這唯一的ASCII碼啊，這就可以作為數組索引的目錄。 (```) #include<stdio.h> #include<string.h> int main() { char a1[100000]; char b1[100000]; int c[128] = { 0 };//初始化這個數組的的所有元素都為0 gets(a1); gets(b1); for (int i = 0; i <strlen(a1); i++) { if (c[a1[i]] == 0) { c[a1[i]] = 1; printf("%c",a1[i]); } } for (int i = 0; i < strlen(b1); i++) { if (c[b1[i]] == 0) { c[b1[i]] = 1; /*每當出現一個新字元就講b1[i]在c中對應的值改成1，當之後讀取到c[b1[i]]==1時，程式就知道b1[i]在之前出現過了*/ printf("%c",b1[i]); } } return 0; } (```) 這樣我們就完成了對字元串的去重處理，時間複雜度O(n)，在OJ中更有優勢。當然這隻是數組標記法在本題中中的一個小小應用，至少在PTA中這個方法屢試不爽，希望大家都能夠運用好此方法，為自己的演算法刷題錦上添花。
