从数组中删除重复字符

Question

在阅读Gayle Laakmann的书《Cracking the coding interview》时，我遇到了这个问题：

设计一个算法并编写代码，在不使用任何额外缓冲区的情况下删除字符串中的重复字符。注意：使用一两个额外变量是可以的，但不能使用数组的额外副本。

以下是代码：

 public static void removeDuplicates(char[] str) {
        if (str == null) {
            return;
        }
        int len = str.length;
        if (len < 2) {
            return;
        }

        int tail = 1;

        for (int i = 1; i < len; ++i) {
            int j;
            for (j = 0; j < tail; ++j) {
                if (str[i] == str[j]) {
                    break;
                }
            }
            if (j == tail) {
                str[tail] = str[i];
                ++tail;
            }
        }
        str[tail] = 0;
    }

这段代码旨在从数组中删除重复字符。我不太理解算法是通过反复替换相同的字符来实现的。我以为只有我觉得算法不起作用，但实际上当我运行这段代码时，它给出了错误的输出。这是书中的严重错误还是我没有理解问题？

- TCM

Answer 1

算法似乎是有效的，但没有清除剩余字符。 将代码更改为以下内容即可解决问题： 注意：替换为：

str[tail] = 0;

使用：

    for(; tail < len;tail++){
        str[tail] = 0;
    }

---

public static void removeDuplicates(char[] str) {
        if (str == null) {
            return;
        }
        int len = str.length;
        if (len < 2) {
            return;
        }

        int tail = 1;

        for (int i = 1; i < len; ++i) {
            int j;
            for (j = 0; j < tail; ++j) {
                if (str[i] == str[j]) {
                    break;
                }
            }

            if (j == tail) {
                str[tail] = str[i];
                ++tail;
            }

        }
        for(; tail < len;tail++){
            str[tail] = 0;
        }

    }

- YoK

---

对于 char[] str = {'a','a'}; 它会输出 [a, ]。 - EMM

Answer 2

使用位向量的解决方案。

时间复杂度: O(n)，其中 n = 字符串长度

空间复杂度: O(1)

void removeduplicatas(char str[]){
    int i, checker = 0, bitvalue = 0, value = 0, tail = 0;
    i = 0;
    tail = 0;
    while(str[i]){
        value = str[i] - 'a';
        bitvalue = 1 << value;
        if((checker & bitvalue) == 0 ){
            str[tail++] = str[i];
            checker |= bitvalue;
        }
        i++;
    }
    str[tail] = '\0';
}

- Thiago

Answer 3

在Java中，数组是固定大小的。因此，如果调用函数发现任何重复项，它无法更改输入数组的大小。您的函数只是将具有重复项的子数组的起始索引设置为0。所以当您在调用函数中打印数组内容时，被设置为0的元素不会被打印出来，但随后的元素（如果有的话）会被打印出来。

YoK的答案将子数组中重复的所有元素都设置为0。所以当您在调用函数中打印它时，重复项不会被打印出来。但请记住，数组的大小仍然没有改变。

另一种方法是返回具有唯一字符的子数组的大小。在您的情况下，这个大小是tail。

还有一种选择是将输入作为StringBuffer传递，并进行原地更改，如下所示：

public static void removeDuplicates(StringBuffer str) {                        

        int len = str.length();

        // if the string as less than 2 char then it can't have duplicates.
        if (len < 2) {                         
                return;
        }

        // fist character will never be duplicate.
        // tail is the index of the next unique character.
        int tail = 1;

        // iterate from 2nd character.
        for (int i = 1; i < len; ++i) {
                int j;

                // is char at index i already in my list of uniq char?
                for (j = 0; j < tail; ++j) {
                        if (str.charAt(i) == str.charAt(j)) {
                                break;
                        }      
                }

                // if no then add it to my uniq char list.
                if (j == tail) {                       
                        str.setCharAt(tail, str.charAt(i));

                        // increment tail as we just added a new ele.
                        ++tail;
                }
        }
        // at this point the characters from index [0,tail) are unique
        // if there were any duplicates they are between [tail,input.length)
        // so truncate the length of input to tail.
        str.setLength(tail);
}

Ideone链接

- codaddict

Answer 4

这是一种使用C++和递归的解决方案，通过循环遍历字符串中的每个字符，并在固定宽度的char中使用上述位字符串方法来进行。您需要确保固定宽字符串比所需的k类型字符要长以进行检查。

#include <cstdint>
#include <iostream>

bool CheckUniqueChars(char *string, uint32_t index, uint32_t checker){

char character = string[index];

if(character=='\0'){
    return true;
}else{
    int value = character - 'a';

    if((checker&(1<<value))>0){
        return false;
    }else{
       checker |= (1<<value);
       return CheckUniqueChars(string,++index,checker);
    }
   }
}


int main(int argc, char *argv[]){

    char *string = argv[1];
    uint32_t idx=0,checker=0;

 if(CheckUniqueChars(string,idx,checker)){
        std::cout << "all characters are unique" << std::endl;
 }else{
    std::cout << "there are duplicate characters" << std::endl;
 }

 return 0;
}

- Ethan Lim

Answer 5

我改进了YoK提供的代码，避免使用

。

for(; tail < len;tail++){
       str[tail] = 0;
}

相反，我们可以在第一个循环中设置为空。

public static void removeDuplicates(char[] str){
    if (str == null) {
        return;
    }
    int len = str.length;
    if (len < 2) {
        return;
    }

    int tail = 1;

    for(int i=1;i<len;++i){
        int j;
        for(j=0;j<tail;++j){
            if(str[i] == str[j]) break;
        }
        if(j==tail){
            str[tail] = str[i];
            if(i!=tail)str[i]=0;
            ++tail;
        }else{
            str[i]=0;
        }

    }
}

- Sangan K

---

那本书中提供的算法确实不起作用。它已经被其他答案（如YoK的答案）进行了更正。我改进了YoK的答案，避免使用另一个for循环，并编辑了我的答案。谢谢。 - Sangan K