Nullen an Ende eines Arrays verschieben

Die Programmiersprache C# und Programmierung im .NET Framework/Mono
Antworten
DerSamu
Beiträge: 35
Registriert: Sa Dez 23, 2017 3:15 pm

Nullen an Ende eines Arrays verschieben

Beitrag von DerSamu » Mo Mär 05, 2018 5:37 pm

Ich habe folgendes Problem:
Ich will zuerst alle doppelten Stellen eines Arrays löschen und danach diese Nullen an das Ende des Arrays verschieben. Das mit den löschen habe ich mehr oder weniger elegant schon geschafft aber irgendwie leuchtet mir nicht ein wie ich die Nullen verschieben kann.
Ich meine klar, zuerst muss man mal den gesamten array durchlaufen und überprüfen wo eine 0 ist. Aber wie verschiebe ich es dann zum Schluss?
Kleine Randnotizen: Ich will keinen neuen Array anlegen und der Array sollte so aussehen:
Vor dem Verdichten: [9 3 1 0 0 2 0 5 6]
nach dem Verdichten: [9 3 1 2 5 6 0 0 0 ]

mfG Samu
lernender Programmierer, hauptsächlich C# und Java

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Nullen an Ende eines Arrays verschieben

Beitrag von Xin » Mo Mär 05, 2018 7:07 pm

Ich würde zwei Indizes nehmen: source und target.

Mit Target gehst Du los und suchst die erste Null - das ist dein Ziel. Das wäre hier der Index 3. Anschließend läufst Du mit Source weiter und suchst die erste Zahl, die keine 0 ist. Das wäre Index 5. Anschileßend vertauscht Du die beiden Werte. Die 2 an INdex 5 wird mit der 0 an Index 3 vertauscht.
Das Array ist dann 931200056.
Target wandert nun weiter auf Index 4. (+1). Source (ist 5) und zeigt nun auf die Null, wo vorher die 2 war. Source sucht nun die nächste Zahl: An Index 6 ist wieder eine 0. An Index 7 aber ist die 5. Wieder vertauschen. Das Array ist nun 931250006.
Target um 1 erhöhen auf Index 5. und Source sucht die nächste Zahl, beginnend bei Index 8. Da ist die 6, vertauschen. Das Array ist nun 931256000.
Target um 1 erhöhen auf Index 6 und Source sucht die nächste Zahl, beginnend bei Index 9. Index 9 ist aber die größe vom Array, da kommt nix mehr
Fertig.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

DerSamu
Beiträge: 35
Registriert: Sa Dez 23, 2017 3:15 pm

Re: Nullen an Ende eines Arrays verschieben

Beitrag von DerSamu » Mo Mär 05, 2018 7:34 pm

Danke für die Gute und schnelle Antwort! So sieht jetzt die Methode aus:

Code: Alles auswählen

public static int[] CompressArray(int[] integers) {
            int source = 0;
            int target = 0;
            int temp;
            while (target < integers.Length) {
                if (integers[target] == 0) {            //Target zeigt die erste 0 im array an
                    while (source < integers.Length) {
                        if (source > target) {
                            if (integers[source] != 0) {       //Source zeigt jetzt die erste Stelle nach der ersten 0 an, welche keine 0 ist
                                temp = integers[target];
                                integers[target] = integers[source];
                                integers[source] = temp;
                                break;
                            }
                        }
                        source++;
                    }
                }
                target++;

            }
            return integers;
        }
Und wie würdet ihr aus einem Array alle doppelten Zahlen durch eine 0 ersetzen(war auch Teil der Aufgabe).
Ich weiß ziemlich sicher, dass meine Lösung nicht die beste ist...

Code: Alles auswählen

public static int[] DeleteDoubles(int[] integers) {
            int counter = 0;
            for (int i = 0; i < integers.Length; i++) {
                counter = 0;
                while (counter < i) {
                    if (integers[counter] == integers[i]) {
                        integers[counter] = 0;
                    }
                    counter++;
                }
            }
            return integers;
        }
Wüsstet ihr, was ich verbessern könnte?
LG Samu
lernender Programmierer, hauptsächlich C# und Java

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Nullen an Ende eines Arrays verschieben

Beitrag von cloidnerux » Mo Mär 05, 2018 11:01 pm

Und wie würdet ihr aus einem Array alle doppelten Zahlen durch eine 0 ersetzen(war auch Teil der Aufgabe).
Man kann es ja mal "formell" angehen:
Deine Lösung ist wrsl die "intuitive" und sollte nach meinem Halbwissen mit O(1/2n^2) im worst case laufen, daher es gibt keine Doppelungen und du musst für jede Stelle einmal durch den Rest des Arrays laufen.
Der "optimale" Algorithmus sollte denke ich in O(n) laufen, daher man muss durch jedes Element einmal durch iterieren.
Weiterhin muss dein Algorithmus für jedes Element eine Entscheidung treffen, ob es ein Duplikat ist oder nicht. Dies kannst du "Vorausschauend" oder "Zurückblickend" implementieren. Du hast es "Vorausschauend" implementiert, daher du findest ein neues Element und schaust nach "vorne", wo das Element noch auftaucht.
Zurückschauend ist dann dementsprechend der Blick zurück, ob das Element schon einmal aufgetaucht ist. Das Iterativ zu lösen ist aber nicht schneller als dein Algorithmus.

Jetzt kann man einmal die Randbedingung setzten, dass dein Raum möglicher Ziffern/Zahlen eingeschränkt ist. Nun legen wir ein Array mit N/8 Bytes an, wobei N die maximal mögliche Anzahl Ziffern ist. Findest du eine neue Ziffer Z, so setzt du das Bit 1<<Z auf 1, möchtest du wissen, ob die Ziffer Z schon vorgekommen ist, Prüfst du das Bit 1<<Z. Dies ist eine lineare Operation.
Natürlich sagst du jetzt, dass das speicheraufwendig ist, was auch stimmt. Jedoch ist das so eine Abwägung die du Treffen kannst oder musst, Geschwindigkeit mit Speicheraufwand zu tauschen und umgekehrt. Zudem ist der Speicheraufwand für realistische Probleme gar nicht so hoch. Nehmen wir mal an, du sollst Postleitzahlen so sortieren. Du hast 5-Stellige Zahlen, daher alles im Bereich von 0 bis 99999. Das sind etwas weniger als 2^17 Bits, daher 2^14 Byte oder 16kB Speicherbedarf.

Wenn du den vollen 32-Bit Zahlenraum hast, bräuchtest du 2^28 Byte Speicher, 1/4GB, das ist möglicherweise etwas viel.

Eine ähnliches Prinzip, aber nur Mathematisch relevant: Wenn du eine Funktion P(n) hast, die dir die n-te Primzahl liefert, kannst du einfach ein Produkt PZ mitlaufen lassen. Mit jeder neuen Ziffer Z die du findest Multiplizierst du dein Produkt PZ mit P(Z). Die Überprüfung, ob eine Zahl schon vorgekommen ist, ist PZ % P(Z) == 0
Redundanz macht wiederholen unnötig.
quod erat expectandum

Orioner
Beiträge: 102
Registriert: Mo Dez 10, 2012 10:52 am

Re: Nullen an Ende eines Arrays verschieben

Beitrag von Orioner » Fr Jun 01, 2018 6:59 pm

Ich würde es so machen:
Du guckst dir der Reihe nach jedes Element, ausgehend vom ersten, an und prüfst, ob es eine Null ist. Wenn ja, vertauschst du es mit dem nachfolgenden Element. Wenn du das ganze Array durch hast, fängst du wieder von vorne an, allerdings nicht beim ersten Element, sondern beim zweiten. Bein dritten Durchlauf beginnst du beim dritten, usw. Mit einer verschachtelten Schleife sollte das möglich sein. Das sollte nicht langsamer sein, als der BubbleSort-Algorithmus.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Nullen an Ende eines Arrays verschieben

Beitrag von Xin » So Jun 03, 2018 7:00 am

Orioner hat geschrieben:Ich würde es so machen:
Du guckst dir der Reihe nach jedes Element, ausgehend vom ersten, an und prüfst, ob es eine Null ist. Wenn ja, vertauschst du es mit dem nachfolgenden Element. Wenn du das ganze Array durch hast, fängst du wieder von vorne an, allerdings nicht beim ersten Element, sondern beim zweiten. Bein dritten Durchlauf beginnst du beim dritten, usw. Mit einer verschachtelten Schleife sollte das möglich sein. Das sollte nicht langsamer sein, als der BubbleSort-Algorithmus.
Das sollte wirklich nicht langsamer sein, denn das ist der Bubblesort.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Antworten