Entfernen von doppelten Zeichen aus array

Während Sie Lesen ein Buch namens Cracking the coding interview durch Gayle Laakmann stieß ich auf diese Frage

Entwerfen Sie einen Algorithmus und schreiben Sie den code zum entfernen der doppelte Zeichen
in einem string ohne zusätzlichen Puffer. HINWEIS: Eine oder zwei
weitere Variablen sind in Ordnung. Eine zusätzliche Kopie des Arrays 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;
    }

entfernen soll doppelte Zeichen aus dem array. Ich glaube nicht, ruhig scheinen zu verstehen, was der Algorithmus tut, durch den Austausch den gleichen Charakter immer und immer wieder. Ich dachte, es ist nur mir, wer fühlt, dass der Algorithmus nicht funktioniert, aber ehrlich gesagt, bei mir lief dieser code ermöglicht mir falsche Ausgänge. Ist diese schwerwiegenden Fehler im Buch oder hab ich die Frage nicht verstanden?

InformationsquelleAutor TCM | 2010-08-03

Algo scheint zu funktionieren, aber nicht deaktivieren, übrig gebliebene Zeichen.
Geänderte code Folgendes ein, 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;
        }

    }

dieser code schlägt fehl, wenn der Eingang "aa"
für char[] str = {'a','a'}; es gibt [einen, ]

InformationsquelleAutor YoK

Einer Lösung mit einem bit-Vektor.

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

Platz: 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';
}

InformationsquelleAutor Thiago

In Java sind arrays mit fester Größe. Damit die aufgerufene Funktion kann nicht ändern Sie die Größe des Arrays input, wenn es findet alle Duplikate. Ihre Funktion ist nur der start-index des sub-array die Duplikate zu 0. Also, wenn Sie drucken Sie das array-Inhalt in die aufrufende Funktion das element, das gemacht worden ist 0 nicht gedruckt, sondern Elemente Folgen (wenn überhaupt) bekomme gedruckt.

Die Antwort von YoK macht alle Elemente des sub-Arrays, die Duplikate sind auf 0. So dass, wenn Sie es gedruckt in der aufrufenden Funktion, die Duplikate nicht gedruckt werden. Aber Sie müssen Bedenken, dass die Größe des Arrays ist immer noch unverändert.

Alternativ können Sie wieder die Größe der sub-array die einzigartige Zeichen. Die in Ihrem Fall ist tail.

Eine weitere alternative ist die übergabe der input-als StringBuffer und nehmen Sie die änderungen in-place als:

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

dieser code verursacht einen Fehler auf input-string "aa".

InformationsquelleAutor codaddict

Ist dies eine Lösung mit C++ und Rekursion, um eine Schleife durch jedes Zeichen der Zeichenfolge und unter Verwendung der oben genannten Methode bitstring in eine Feste Breite, char. Sie müssen sicherstellen, dass die Feste Breite Zeichenkette ist länger als die erforderlichen k-Typ-Zeichen zu prüfen.

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

InformationsquelleAutor Ethan Lim

Improvisierte ich code von YoK zu vermeiden, mit

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

Stattdessen können wir uns set blank in der ersten Schleife.

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

    }
}

Es ist wahr, dass der Algorithmus in diesem Buch nicht funktioniert. Es wurde bereits korrigiert, andere Antworten wie Antwort mit YoK. Ich verbesserte YoK Antwort zu vermeiden, mit einer anderen for-Schleife bearbeitet meine Antwort. Danke.

InformationsquelleAutor Sangan K

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.