1_3.md

数组与字符串系列(3)

题目

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

解法

public void removeDuplicate(char[] str) {
    if (null == str || str.length == 0) {
        return;
    }
    int len = str.length;
    int newIdx = 0;
    for (int i = 0; i < len; ++i) {
        if (str[i] != '\0') {
            str[newIdx] = str[i];
            for (int j = i + 1; j < len; ++j) {
                if (str[newIdx] == str[j]) {
                    str[j] = '\0';
                }
            }
            newIdx++;
        }
    }
    if (newIdx > 1) {
        --newIdx;
    }
    str[newIdx] = '\0';
}

简要分析

时间复杂度为O(n^2)