刪除重複的字符數組從

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

    } 
}