Entfernen von doppeltem Charakter von Array

Question

Während ein Buch Cracking the coding interview von Gayle Laakmann namens lesen, ich kam in dieser Frage

Entwurf einen Algorithmus und Code schreiben, um die doppelten Zeichen in einer Zeichenfolge zu entfernen, ohne dass zusätzliche Puffer. HINWEIS: Ein oder zwei zusätzliche Variablen sind in Ordnung. Eine zusätzliche Kopie des Arrays ist nicht.

und dieser Code: -

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

die doppelte Zeichen aus dem Array entfernen soll. Ich verstehe nicht, was der Algorithmus tut, indem ich das gleiche Zeichen immer wieder ersetze. Ich dachte, dass nur ich der Meinung bin, dass der Algorithmus nicht funktioniert, aber tatsächlich, wenn ich diesen Code lief, gibt er mir falsche Ausgaben. Ist das ein ernster Fehler im Buch oder habe ich die Frage nicht verstanden?

Answer 1

Algo scheint zu arbeiten, aber nicht übrig gebliebene Zeichen zu löschen. Geänderte Code zu folgen und es funktioniert: Hinweis: Ersetzt:

str[tail] = 0; 

mit:

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

In Java-Arrays sind eine feste Größe. Daher kann die aufgerufene Funktion die Größe des Eingabearrays nicht ändern, wenn sie Duplikate findet. Ihre Funktion erstellt nur den Startindex des Sub-Arrays, das Duplikate enthält, in 0. Wenn Sie also den Array-Inhalt in der aufrufenden Funktion drucken, wird das Element 0 nicht gedruckt, aber Elemente, die darauf folgen (falls vorhanden), werden gedruckt.

Die Antwort von YoK macht alle Elemente des Sub-Array, die Duplikate sind 0. So, wenn Sie es in der aufrufenden Funktion drucken, werden die Duplikate nicht gedruckt. Aber Sie müssen daran denken, dass die Größe des Arrays unverändert bleibt.

Alternativ können Sie die Größe des Unterfelds mit eindeutigen Zeichen zurückgeben. Was in Ihrem Fall ist tail.

Eine weitere Alternative ist, die Eingabe als StringBuffer passieren und die Änderungen in-place machen, wie:

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

eine Lösung mit einem Bit-Vektor verwendet wird.

Zeit: O (n), wobei n = length of the string

Raum: 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

Dies ist eine Lösung, mit C++ und Rekursion durch jedes Zeichen der Zeichenfolge-Schleife und unter Verwendung der obigen Methode der Bitstring in einer festen Breite char. Sie müssen sicherstellen, dass die feste breite Zeichenfolge länger ist als die erforderlichen k-Zeichen, die überprüft werden sollen.

#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

improvisierten I-Code von Yok gegeben zu vermeiden

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

Stattdessen verwenden wir selbst leer in der ersten Schleife festlegen.

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

    } 
}