Extracción de carácter duplicado de la matriz

Question

Durante la lectura de un libro llamado Cracking the coding interview por Gayle Laakmann, me encontré con esta pregunta

Diseño de un algoritmo y escribir código para eliminar los caracteres duplicados en una cadena sin necesidad de utilizar cualquier tampón adicional. NOTA: Una o dos variables adicionales están bien. Una copia extra de la matriz no es.

y este código: -

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

que se supone que para eliminar el carácter duplicado de la matriz. No me parece tranquilo entender lo que está haciendo el algoritmo al reemplazar al mismo personaje una y otra vez. Pensé que solo soy yo quien siente que el algoritmo no funciona, pero de hecho cuando ejecuté este código me está dando resultados incorrectos. ¿Es este error grave en el libro o no he entendido la pregunta?

Answer 1

Parece que algo está funcionando, pero no borra los caracteres sobrantes. código cambiado a seguir y funciona: Nota: se ha sustituido:

str[tail] = 0; 

con:

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

En las matrices de Java son de tamaño fijo. Entonces, la función llamada no puede cambiar el tamaño de la matriz de entrada si encuentra algún duplicado. Su función es simplemente hacer que el índice de inicio de la sub-matriz tenga duplicados en 0. Por lo tanto, cuando imprime los contenidos de la matriz en la función de llamada, el elemento que se ha creado 0 no se imprime, pero los elementos que lo siguen (si hay alguno) se imprimen.

La respuesta de YoK hace que todos los elementos del subarreglo que están duplicados sean 0. De modo que cuando lo imprima en la función de llamada, los duplicados no se impriman. Pero debe recordar que el tamaño de la matriz aún no se ha modificado.

Como alternativa, puede devolver el tamaño de la sub-matriz que tiene caracteres únicos. Que en su caso es tail.

una alternativa más es pasar la entrada como una StringBuffer y hacer los cambios en el lugar como:

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

Una solución usando un vector de bits.

Tiempo: O (n), donde n = length of the string

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

Esta es una solución usando C++ y la recursión a bucle a través de cada carácter de la cadena y con el anteriormente método de cadena de bits en un char de ancho fijo. Debe asegurarse de que la cadena ancha fija sea más larga que los caracteres de tipo k necesarios para verificar.

#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

improvisé código dado por Yok evitar el uso de

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

su lugar, podemos establecer en blanco en primer bucle en sí.

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

    } 
}