CareerCup之1.3字符串去重

【题目】

原文：

1.3 Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer. NOTE: One or two additional variables are fine. An

extra copy of the array is not.

FOLLOW UP

Write the test cases for this method.

译文：

设计算法并写出代码移除字符串中重复的字符，不能使用额外的缓存空间。注意： 可以使用额外的一个或两个变量，但不允许额外再开一个数组拷贝。

【分析】

这道题目其实是要你就地(in place)将字符串中重复字符移除。你可以向面试官问清楚， 不能使用额外的一份数组拷贝是指根本就不允许开一个数组，还是说可以开一个固定大小， 与问题规模(即字符串长度)无关的数组。

根据面试官的回答，制定相应的解题策略。

【思路一】

如果根本就不允许你再开一个数组，只能用额外的一到两个变量。那么，最先想到的方法就是暴力求解法了。

你可以依次访问这个数组的每个元素，每访问一个，就将该元素与前面的元素进行比较，如果相同就去掉，如果不相同就添加到前面序列中。

时间复杂度为O（n^2）

相应代码为代码一

【思路二】

如果根本就不允许你再开一个数组，只能用额外的一到两个变量。第二种方法就是先排序，再去重。

排序之后重复元素必定是相邻的，这样去重就简单多了。

排序时间复杂度最快为快速排序为O（nlogn）

去重时间复杂度为O（n）

最终为O（nlogn）

相应代码为代码二

【思路三】

1 如果可以开一个固定大小，与问题规模(即字符串长度)无关的数组，那么可以用一个数组来 表征每个字符的出现(假设是ASCII字符，则数组大小为256)，这样的话只需要遍历一遍字符 串即可，时间复杂度O(n)。

相应代码为代码三

2 如果字符集更小一些，比如只是a-z，即字符串里只包含小写字母，那么使用一个int变量中 的每一位来表征每个字符的出现，用位运算来实现。也可以在O(n)的时间里移除重复字符，而且还不需要额 外开一个数组。

相应代码为代码四

【代码一】

/*********************************
*   日期：2014-5-6
*   作者：SJF0115
*   题目: 字符串中字符去重
*   来源：CareerCup
**********************************/
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

//删除一个字符串中重复字符
void RemoveDuplicates(char str[]){
    int i,j;
    if(str == NULL){
        return;
    }
    int len = strlen(str);
    //去重
    int index = 0;
    for(i = 0;i < len;i++){
        //str[i]为待考察的元素 与前面元素比较看是否重复
        for(j = 0;j < i;j++){
            //有重复的元素
            if(str[i] == str[j]){
                break;
            }
        }
        //str[i] 前面没有与之重复的元素
        if(j >= i){
            str[index++] = str[i];
        }
    }
    str[index] = '\0';
}

int main() {
    char str[] = "abababa";
    RemoveDuplicates(str);
    cout<<str<<endl;
    return 0;
}

【代码二】

//删除一个字符串中重复字符
void RemoveDuplicates(char str[]){
    if(str == NULL){
        return;
    }
    int len = strlen(str);
    //排序
    sort(str,str+len);
    int index = 1;
    //去重
    for(int i = 1;i < len;i++){
        if(str[i] != str[i-1]){
            str[index++] = str[i];
        }
    }
    str[index] = '\0';
}

【代码三】

//删除一个字符串中重复字符
void RemoveDuplicates(char str[]){
    bool vis[256];
    //初始化
    memset(vis,false,sizeof(vis));
    int len = strlen(str);
    int index = 0;
    for(int i = 0;i < len;i++){
        if(!vis[str[i]]){
            str[index++] = str[i];
            vis[str[i]] = true;
        }
    }
    str[index] = '\0';
}

【代码四】

void RemoveDuplicates(char str[]){
    int len = strlen(str);
    if(len < 2) return;
    int check = 0;
    int index = 0;
    //去重
    for(int i=0; i<len; ++i){
        int v = (int)(str[i]-'a');
        if((check & (1<<v))==0){
            str[index++] = str[i];
            check |= (1<<v);
        }
    }
    str[index] = '\0';
}