Удаление дубликатов из массива символов

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

Algo похоже работает, но не очищает оставшиеся символы. Изменен код следующий, и она работает: Примечание: Заменено:

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

решение с использованием битового вектора.

Время: О (п), где 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; 
     } 

    } 
}