Le moyen le plus rapide de trouver les doublons dans une chaîne de caractères sans utiliser de mémoire supplémentaire en java ?

Question

Quel est le moyen le plus rapide de supprimer un caractère en double dans une chaîne sans utiliser de mémoire supplémentaire en Java ?

Answer 1

Utilisez indexOf y delete méthodes en StringBuilder .

Answer 2

Comme une chaîne de caractères est immuable, vous ne pourrez pas la modifier. Par conséquent, la nouvelle version de la chaîne sans le caractère en double consommera de la mémoire. Si vous donnez plus de détails sur l'objectif et le raisonnement de votre demande, quelqu'un pourra peut-être vous proposer une meilleure approche.

Answer 3

Comme les chaînes de caractères sont immuables en Java, vous aurez besoin de au moins une copie, quoi qu'il arrive. La meilleure solution consiste donc à utiliser un tableau de caractères et System.arraycopy. D'autres alternatives sont StringBuilder/StringBuffer et CharBuffer . J'espère que cela vous aidera.

Answer 4

Les chaînes sont immuables. En réalité, vous devrez allouer de la mémoire supplémentaire.

Puisque vous dites le plus rapide, je suppose que vous n'envisagerez pas un algorithme à deux passages. Vous pouvez utiliser StringBuilder mais cela allouera votre longueur de chaîne originale + 16, et, lorsque vous appelez getString() vous allouerez à nouveau de la mémoire dans le constructeur String.

Si vous n'avez pas peur d'avoir un algorithme à deux passes, vous avez deux allocations d'un char[] (de la longueur finale de la chaîne nettoyée). Utilisez un StringBuilder et vous aurez besoin de 2*len + 16, mais ce sera plus rapide.

Answer 5

Vous devez utiliser un StringBuilder . Cependant, voici une méthode avec laquelle vous pouvez vous tirer une balle dans le pied :

    String s = "bookkeepers";
    Class<?> c = String.class;
    Field field = c.getDeclaredField("value");
    field.setAccessible(true);
    char[] value = (char[]) field.get(s);
    // remove duplicate characters
    char last = 0;
    int len = 0;
    int writePtr = 0;
    for(int i = 0; i < value.length; i++) {
        value[writePtr] = value[i];
        if (value[i] != last) {
            writePtr++;
            last = value[i];
            len++;
        }
    }
    Field count = c.getDeclaredField("count");
    count.setAccessible(true);
    count.set(s, len);

    System.out.println(s);

Sortie bokepers