删除重复的字符数组从

Question

在阅读名为Cracking the coding interview由Gayle Laakmann一本书，我遇到了这个问题

设计算法和编写代码来删除字符串中的字符重复不 使用任何额外的缓冲。注意：一个或两个 附加变量都可以。数组的额外副本不是。

和验证码 -

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; 
    } 

这是应该从数组中删除重复的字符。我不安静，似乎通过一次又一次地替换相同的字符来理解算法在做什么。我认为只有我觉得算法不起作用，但实际上当我运行这段代码时，它给了我错误的输出。这是书中的严重错误还是我没有理解这个问题？

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; 
     } 

    } 

Answer 2

在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 Link

Answer 3

使用位向量中的溶液。

时间：O（n），其中n = length of the string

空间：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'; 
} 

Answer 4

这是使用C++和递归遍历所述串的每一字符，并且使用上述的一个解决方案一个固定宽度字符中的位串的方法。您需要确保固定的宽字符串比检查所需的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; 
} 

Answer 5

我即兴由郁慕明给出避免使用

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; 
     } 

    } 
}