Удаление повторяющегося символа из массива

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

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

Время: 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 3

Это одно решение, использующее C ++ и рекурсию для циклического прохождения каждого символа строки и использующее описанный выше метод bitstring в символе фиксированной ширины. Необходимо убедиться, что фиксированная широкая строка длиннее, чем необходимые символы 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 4

В 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 5

Я импровизировал код, данный YoK, чтобы избежать использования

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

    }
}