字符串去重 C++多种方法

除了使用哈希表和双指针的方法，还可以使用其他方法来实现字符串去重。下面介绍几种常见的方法：

1. 排序去重法

将字符串排序后，遍历字符串中的每个字符，如果该字符不等于前一个字符，则将该字符加入结果字符串中。这种方法的时间复杂度为 O(nlogn)，空间复杂度为 O(n)。

代码如下：

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string remove_duplicate_chars(string s) {
    sort(s.begin(), s.end());
    string result;
    for (int i = 0; i < s.size(); i++) {
        if (i == 0 || s[i] != s[i-1]) {
            result += s[i];
        }
    }
    return result;
}

int main() {
    string s = "abcaabbcc";
    string result = remove_duplicate_chars(s);
    cout << result << endl;  // 输出：abc
    return 0;
}

2. 暴力枚举法

遍历字符串中的每个字符，判断该字符在字符串中是否重复出现，如果没有则将该字符加入结果字符串中。这种方法的时间复杂度为 O(n^2)，空间复杂度为 O(n)。

代码如下：

#include <iostream>
#include <string>

using namespace std;

string remove_duplicate_chars(string s) {
    string result;
    for (int i = 0; i < s.size(); i++) {
        bool found = false;
        for (int j = 0; j < i; j++) {
            if (s[j] == s[i]) {
                found = true;
                break;
            }
        }
        if (!found) {
            result += s[i];
        }
    }
    return result;
}

int main() {
    string s = "abcaabbcc";
    string result = remove_duplicate_chars(s);
    cout << result << endl;  // 输出：abc
    return 0;
}

3. 位图法

使用一个长度为 256 的布尔型数组，将字符串中每个字符的 ASCII 码作为数组下标，并将对应的数组元素置为 true。这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)。

代码如下：

#include <iostream>
#include <string>

using namespace std;

string remove_duplicate_chars(string s) {
    bool bitmap[256] = {false};
    string result;
    for (int i = 0; i < s.size(); i++) {
        int index = (int)s[i];
        if (!bitmap[index]) {
            bitmap[index] = true;
            result += s[i];
        }
    }
    return result;
}

int main() {
    string s = "abcaabbcc";
    string result = remove_duplicate_chars(s);
    cout << result << endl;  // 输出：abc
    return 0;
}

需要注意的是，这种方法只能处理 ASCII 码范围内的字符，无法处理 Unicode 码。