Hallo zusammen,
Ich habe folgende Aufgabe: Erstelle eine Methode, die ein char[] nimmt, doppelte Werte erkennt und ein anderes char[] zurückliefert, dass nur aus eindeutigen Werten besteht. Es dürfen keine zusätzlichen Klassen oder Techniken wie Generics benutzt werden.
Ich habe die Methode folgendermassen implementiert, ich hoffe, man kann den Kommentaren einigermassen folgen:
Der Algorithmus funktioniert. Übergebe ich z.B. {'h','a','l','l','o'}, erhalte ich {'h','a','l','o'}.
Nun, ich werde das Gefühl nicht los, dass der Algorithmus a) unschön / unlesbar ist und b) ineffizient. In der zweiten For-Schleife im unteren Teil kam ich nicht umhin, ein weiteres Array boolean[] temp zu verwenden. Zuerst wollte ich es ohne dies tun, aber mir kam einfach nicht in den Sinn, wie ich verhindern konnte, dass wenn z.B.
in = {'h','a','l','l','o'}
und somit
isDouble = {false, false, false, true, false}
ist,
das resultiertende Array out = {'h','a','l','l'} war, weil jedesmal i = j gesetzt wird.
Wer jetzt noch weiss, um was es geht - hut ab!
Ausserdem wird z.B. die 1. Schleife, falls sich der erste wert von allen nachfolgenden unterscheidet, mindestens n*n ausgeführt, und im schlechtesten fall noch viel mehr. (n = in.length)
Ich bin noch nicht so erfahren mit effizientem, schönen Programmieren und hoffe ihr könnt mir helfen.
Lieber Gruss
Ich habe folgende Aufgabe: Erstelle eine Methode, die ein char[] nimmt, doppelte Werte erkennt und ein anderes char[] zurückliefert, dass nur aus eindeutigen Werten besteht. Es dürfen keine zusätzlichen Klassen oder Techniken wie Generics benutzt werden.
Ich habe die Methode folgendermassen implementiert, ich hoffe, man kann den Kommentaren einigermassen folgen:
Java:
/**
* Removes duplicate characters from an array of characters.
* The resulting array will consist of unique values only.
* @param in
* @return
*/
public static char[] removeDuplicates(char[] in){
char[] out;
boolean[] isDouble = new boolean[in.length];
int counter = in.length;
// iterate through in, set isDouble true for duplicate values
for (int i = 0; i < in.length; i++) {
if(!isDouble[i]){
for (int j = i + 1; j < in.length; j++) {
if(!isDouble[j]){
if(in[i] == in[j]){
isDouble[j] = true;
counter--;
}
}
}
}
}
// assertion: for every duplicate value in[k], isDouble[k] = true
// assertion: counter equals the size of the array with only unique values
// compute out[]
out = new char[counter];
boolean[] temp = new boolean[in.length];
// since out and in won't have the same size, only add unique values from in to out
for (int i = 0; i < out.length; i++) {
int j = i;
boolean breakThis = false;
while(j < in.length && !breakThis){
if(!isDouble[j] && !temp[j]){
out[i] = in[j];
breakThis = true; // breaks the while loop, so that out[i] is not overwritten by
// following unique in[j]
temp[j] = true; // if true, assignment is skipped even when in[j] is a unique value;
// this avoids that one unique value is assigned to both out[i] and out[i+1]
}
j++;
}
}
return out;
}Der Algorithmus funktioniert. Übergebe ich z.B. {'h','a','l','l','o'}, erhalte ich {'h','a','l','o'}.
Nun, ich werde das Gefühl nicht los, dass der Algorithmus a) unschön / unlesbar ist und b) ineffizient. In der zweiten For-Schleife im unteren Teil kam ich nicht umhin, ein weiteres Array boolean[] temp zu verwenden. Zuerst wollte ich es ohne dies tun, aber mir kam einfach nicht in den Sinn, wie ich verhindern konnte, dass wenn z.B.
in = {'h','a','l','l','o'}
und somit
isDouble = {false, false, false, true, false}
ist,
das resultiertende Array out = {'h','a','l','l'} war, weil jedesmal i = j gesetzt wird.
Wer jetzt noch weiss, um was es geht - hut ab!
Ausserdem wird z.B. die 1. Schleife, falls sich der erste wert von allen nachfolgenden unterscheidet, mindestens n*n ausgeführt, und im schlechtesten fall noch viel mehr. (n = in.length)
Ich bin noch nicht so erfahren mit effizientem, schönen Programmieren und hoffe ihr könnt mir helfen.
Lieber Gruss
Zuletzt bearbeitet:
