数组标记法在算法题中的应用

#数组标记法在算法题中的应用

什么？！你还不知道数组在算法题中不仅起储存数据的作用，还可以起链接标记的作用？哈哈不要紧，原来我也是不知道的，我是看了我好哥们的做题思路才知道这个方法的。。。

----

我们先声明一个长度为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中这个方法屡试不爽，希望大家都能够运用好此方法，为自己的算法刷题锦上添花。