Alle Zeichen verschieben

EinNutzer0

Hallo,

ich möchte alle Zeichen einer Zeichenfolge um shift Schritte in eine Richtung verschieben. Es soll dabei kein zusätzliches Array benutzt werden und aus performancegründen soll der Algorithmus nicht mehr als O(n), wenn n die Länge der Zeichenfolge ist, Schritte brauchen...

Das ist mein bisheriger Ansatz:

    public static char[] shiftImproved(final char[] txt, final int shift) {
        for (int i = 1; shift * (i - 1) + shift <= txt.length; i *= 2) {
            for (int j = 0; j < shift; j++) {
                int i1 = (shift * (i - 1) + j) % txt.length;
                int i2 = (shift * (i - 1) + j + shift) % txt.length;
                char temp = txt[i1];
                txt[i1] = txt[i2];
                txt[i2] = temp;
            }
        }
        System.out.println("txt = " + Arrays.toString(txt));
        return txt;
    }

    public static void main(String[] args) {
        for (int i = 1; i < 10; i++) {
            System.out.println("i = " + i);
            shiftImproved("Guten Tag".toCharArray(), i);
        }
    }

Und das ist die Ausgabe:

i = 1
txt = [u, t, G, n, e, , T, g, a]
i = 2
txt = [a, e, n, , G, u, g, t, T]
i = 3
txt = [e, n, , T, a, g, G, u, t]
i = 4
txt = [u, t, e, a, g, n, , T, G]
i = 5
txt = [n, T, a, g, , G, u, t, e]
i = 6
txt = [e, n, , T, a, g, G, u, t]
i = 7
txt = [t, e, n, , T, g, a, G, u]
i = 8
txt = [u, t, e, n, , T, a, g, G]
i = 9
txt = [G, u, t, e, n, , T, a, g]

Sieht vielleicht jemand (schnell), was ich falsch mache - oder warum nur die Hälfte der Ausgaben richtig ist? Danke.

Also, noch mal kurz zusammengefasst:

Speicherplatzanforderung: O(1)
Laufzeitanforderung: O(n)

Th69

Und warum hast du dann eine doppelt verschachtelte Schleife?

EinNutzer0

@Th69 sagte in Alle Zeichen verschieben:

Und warum hast du dann eine doppelt verschachtelte Schleife?

Das ist zwar eine doppelte Schleife, hat aber O(n).

Ich habe jetzt noch eine andere Lösung, die aber noch nicht in den Fällen richtig funktioniert, in denen shift ein Teiler von der Eingabelänge ist:

    public static char[] shiftImproved(final char[] txt, final int shift) {
        int position = 0;
        char temp = txt[0];
        for (int i = 0; i < txt.length; i++) {
            position = (position + shift) % txt.length;
            char temp2 = txt[position];
            txt[position] = temp;
            temp = temp2;
            if (position == 0 && txt.length % shift == 0) {
                position = 1;
                temp = txt[1];
            }
        }
        System.out.println("txt = " + Arrays.toString(txt));
        return txt;
    }

    public static void main(String[] args) {
        for (int i = 1; i < 15; i++) {
            System.out.println("i = " + i);
            shiftImproved("Guten Tag".toCharArray(), i);
        }
        for (int i = 1; i < 15; i++) {
            System.out.println("i = " + i);
            shiftImproved("Guten Tag!".toCharArray(), i);
        }
    }

i = 1
txt = [g, G, u, t, e, n, , T, a]
i = 2
txt = [a, g, G, u, t, e, n, , T]
i = 3
txt = [T, n, t, G, u, , e, u, g]

Bei i=3 kracht es (9%3==0)... Die if-Bedingung in Zeile 9 behandelt solche Fälle noch nicht richtig.

Th69

@EinNutzer0 sagte in Alle Zeichen verschieben:

Das ist zwar eine doppelte Schleife, hat aber O(n).

Nein, denn shift ist ein Wert von 0 bis N, d.h. im Mittel N/2, also insgesamt O(N*N).

Wenn es keine Hausaufgabe für dich ist, dann kannst du einfach Collections.rotate(List<type> list, int distance) benutzen.
Ansonsten schau auch mal in Fastest algorithm for circle shift N sized array for M position sowie Right rotate an array k times (letzter Code).

EinNutzer0

@Th69 sagte in Alle Zeichen verschieben:

Nein, denn shift ist ein Wert von 0 bis N, d.h. im Mittel N/2, also insgesamt O(N*N).

Oh doch, ist letztendlich aber auch egal, weil er ja nicht funktioniert...

@Th69 sagte in Alle Zeichen verschieben:

dann kannst du einfach Collections.rotate(List<type> list, int distance) benutzen

Kein zusätzliches Array/ List.

@Th69 sagte in Alle Zeichen verschieben:

Ansonsten schau auch mal in Fastest algorithm for circle shift N sized array for M position sowie Right rotate an array k times (letzter Code)

Danke, der letzte Code vom zweiten Link könnte es sein.