Doppelte Werte aus Array entfernen ohne Import - Algorithmus

[barodscheff]

Hallo Leute,

nachdem mir letztes Mal so gut geholfen wurde, habe ich heute wieder ein Problem bei dem ich nicht so recht weiterkomme.

Ich habe eine Methode die ein int-Array erhält. Dieses Array soll ohne doppelte Werte ausgegeben werden. Die Hürde hierbei ist, dass ich keine importierten Klassen verwenden darf. Ich muss also einen Algorithmus erstellen.

Mein Ansatz sieht wie folgt aus:

public class Joker {
    
    static int[] copyRemove(int[] a) {
	
	// Hilfs-Array -> unschöne Lösung
	int[] b = new int[a.length];
	
	int counter = 0;	
	boolean gleich = false;
	
	// Zählen der nicht-doppelten Werte
	for (int i = 0; i < a.length; i++) {
	    for (int j = 0; j < b.length; j++) {
		if (a[i] == b[j]) {
		    gleich = true;
		    break;
		} else {
		    gleich = false;
		}
	    }
	    if (gleich = false) {
		b[counter] = a[i];
		counter++;
	    }
	}
	
	// Array in das kopiert wird
	int[] c = new int[counter];
	
	for (int i = 0; i < c.length; i++) {
	    c[i] = b[i];
	}
	
	return c;
    }

    public static void main(String[] args) {
	int[] eingabe = {1, 3, 3, 5, 1, 12, 6, 1};
	int[] ausgabe = copyRemove(eingabe);
	for (int i = 0; i < ausgabe.length; i++) {
	    System.out.print(ausgabe[i] + " ");
	}
    }

}

Leider hat der Code 1. einen Fehler, sodass mir kein Ergebnis angezeigt wird und 2. finde ich meine Lösung über ein Hilfsarray irgendwie zu kompliziert. Ich denke das muss irgendwie einfacher gehen, ich komme aber nicht drauf.

Hat jemand von euch eine Idee wie ich das schöner lösen kann?

LG

 

[barodscheff]

Ok, ich habe den Fehler gefunden.
Bei der if-Abfrage musste ich == statt = schreiben.

Dennoch ist der Code mMn unnötig lang. Es bleibt also weiter die Frage ob jemand Verbesserungsvorschläge hat. Nochmal: Das Array soll ohne doppelte Werte ausgegeben werden.

public class Joker {
    
    static int[] copyRemove(int[] a) {
	
	// Hilfs-Array -> unschöne Lösung
	int[] b = new int[a.length];
	
	int counter = 0;	
	boolean gleich = false;
	
	// Zählen der nicht-doppelten Werte
	for (int i = 0; i < a.length; i++) {
	    for (int j = 0; j < b.length; j++) {
		if (a[i] == b[j]) {
		    gleich = true;
		    break;
		} else {
		    gleich = false;
		}
	    }
	    if (gleich == false) {
		b[counter] = a[i];
		counter++;
	    }
	}
	
	// Array in das kopiert wird
	int[] c = new int[counter];
	
	for (int i = 0; i < c.length; i++) {
	    c[i] = b[i];
	}
	
	return c;
    }

    public static void main(String[] args) {
	int[] eingabe = {1, 3, 3, 5, 1, 12, 6, 1};
	int[] ausgabe = copyRemove(eingabe);
	for (int i = 0; i < ausgabe.length; i++) {
	    System.out.print(ausgabe[i] + " ");
	}
    }

}

 

[Gucky]

Um das Ganze sauber zu implementieren müsste der Code sogar noch länger werden. 😉

Momentan machst du das mit BruteForce. Das ist zwar einfach aber performancetechnisch eher dürftig. Normalerweise wird zuerst das Array nach Größe sortiert, damit nicht immer jeder Eintrag mit jedem anderen verglichen werden muss, sondern man in linearer Zeit sortieren kann und dann in linearer Zeit die doppelten Einträge suchen kann (sie sind nebeneinander). Gleichzeitig zählst du die Anzahl der nicht doppelten Werte. Anhand dieser Größe erstellst du ein neues Array, in das du deine nicht doppelten Werte kopierst.

Dann kannst du noch das hier:

if (gleich == false) {
       b[counter] = a[i];
       counter++;
}

mit in das else zuvor tun und dahinter ein

break;

ist zwar nicht getestet, müsste aber funktionieren.

 

[barodscheff]

Danke für deine Antwort.

Hm, wenn ich den von dir vorgeschlagenen Teil in das else einfüge, dann vergleicht er doch nur das erste Element von b mit a, oder nicht?

Zum Sortieren hätte ich dann auch noch eine Frage. Der schnellste Sortieralgorithmus läuft doch auch nur in O(n * log(n)). Wenn ich den also durchlaufen lasse und dann noch alle nebeneinander liegenden Elemente vergleiche (es könnten auch mehr als nur 2 gleiche Elemente nebeneinander sein), dann brauche ich doch noch länger als mit meiner spartanischen Lösung oder?!

LG

 

[Gucky]

Bei kleinen Arrays ja aber bei großen Arrays nicht mehr. Bei deiner Lösung steigt die Laufzeit exponentiell. Diese O Notation kenne ich nicht aber exponentiell steigende Laufzeit ist nie gut. 😉 (womöglich wäre es O(n^n))

Was ich mit der Verschiebung des Codes gemeint habe, weiß ich auch nicht mehr. 😀 Ich hab das wohl nicht richtig gelesen. 😀

 

[dcc]

Stell doch einfach die gefunden doppelten Elemente an das Ende/Anfang des Int Arrays und merke dir wie viele es davon gibt. Bei der Ausgabe schneidest das einfach ab.

Das kannst easy mit einer doppelten for schleifen machen. Die äußere iteriert über das Int Array selbst, die innere für jedes Int über die letzten bekannten um zu prüfen ob doppelt. Das müsste mitunter am effizientesten sein, da inplace (im array) alles abläuft.