【OJ】字符串去重并提取出重复字符

　　ACM上一道简单的字符串题，从网上找了下类似的代码进行参考外加之个人思考，想到此好思路。

 

题目大意

---

    任意输入一行字符串，检索重复出现的字符。将原字符串中的重复字符删除后按照原顺序输出，同时按照原顺序输出有哪些字符是重复的。

输入

---

输出

---

　　两个输出之间空一行
    

样例输入

---

    ads_fagaerididfhdus_afiew

样例输出

---

    ads_fgerihuw

    ads_fei

 　　看到此题，第一想法就是用个初始值全为 0 的flag[100000]数组来进行标记，首先是遍历整个字符串，从第i个字符开始与整个字符串所有字符(就不单独把第 i 个字符除开，后面计算时可能有点麻烦，进行判断时 flag[i] == 1 就行了)进行一一比较，如有重复则flag[i] ++ ，最后通过 flag[i] 的值来判断。如果 falg[i] == 1 则打印到屏幕上，但是这样只是把没有重复的字符打印出来，并没有将重复的字符删除而且重复的字符都没有打印到屏幕上，这样明显是不符合题目要求。

　　那要怎样呢？是遍历字符串时把第 i 个字符与字符前或字符后的字符进行对比么，如果这样可以根据各个重复字符的 flag[i] 进行判断，到时只需把 flag[i] == 0 和 flag[i] == 2 打印到屏幕上就可以了。这个对题目中的第一要求删除重复字符按顺序打印到屏幕还过得去，不过第二个按照顺序提取重复的字符又怎么做？因为重复字符出现可不一定是两次，这样 flag[i] 可能为 1、2、3、、4、、、 这样就不要判断了。

　　通过参考网上的代码，那么这个思路就出来了。众所周知，我们键盘输入的字符在ASCII字符集都有对应的ASCII码，把字符的ASCII码一一对应，可以看成一个容量为 128 的数组，字符ASCII的编码就在 0-127 之间嘛。此思路也解决前面那种每个位置上的字符都要一个 flag 空间了，只需要 128 容量的空间就足矣。

　　在这条思路下，我们就初始化所有 flag[128] = {} 在遍历字符串时先判断 flag[str[i]] 是否为 0 因为初始都是 0 所以每个字符对应的 ASCII 码的 flag 都是为 0 的，而在每个进行了判断且满足条件的 flag[str[i]] 都改变其值为 1 （不为0即可），这样当下一个相同字符进行判断时就不满足条件被拒之门外，而所有满足条件的都打印到屏幕上了。这样子题目的第一要求就满足了，

　　那么第二要求呢？还是这个套路，有点像是递归的味道。就之前的判断进行下去，如果进行 str[i] 被拒之门外了怎么办呢？我们还要打印它一次呢，还有它们了中也是有重复的呀。OK ， 旧套路嘛 将上边不满足条件的 flag[str[i]] = 2 (不为 1 就行 为了区分就赋值为 3 吧)。

　　好，这样之后，所有重复的字符ASCII码对应的 flag[str[i]] 的值都为 2 了，就像第一要求那样所有字符对ASCII对应的 flag[str[i]] 都为 0，同样就可以套用第一要求的代码模型啦。再来一个for循环，以 flag[str[i]] == 2 作为判断条件，如果满足条件则将其改变为 3 （不为 2 就行）。这时不满足条件的就不管了，因为已达到要求 那些就没用了，我们将满足条件的打印到屏幕上就行了。

　　最后，代码如下:

 

#include<stdio.h>
#include<string.h>
int main(void)
{
    int i;
    char a[100000];
    int flag[128] = {};
    gets(a);
    for(i = 0; i < strlen(a); i ++)

        if(flag[(int)a[i]] == 0)

        {
            flag[(int)a[i]] = 1;
            printf("%c", a[i]);
        }//删除重复字符后按照原顺序打印
        　　else
            flag[(int)a[i]] = 2;

        printf("\n\n");//空一行
    for(i = 0; i < strlen(a); i ++)
        if(flag[(int)a[i]] == 2)
        {
            flag[(int)a[i]] = 3;
            printf("%c", a[i]);
        }//按照原顺序打印重复字符
}