| 

.NET C# Java Javascript Exception

1
Hallo,
ich soll in Java eine Prozedur
void loescheDuplikate(IntList xl)
erstellen, welche aus einer aufsteigendend sortierten Liste die Duplikate entfernt, sodass jedes Element der Ausgangsliste genau ein mal in der Ergebnisliste vorkommt und dabei soll die bestehende Liste verändert werden!
Der Algorithmus soll in linearer Zeit arbeiten.

Was haltet ihr von dieser Lösung:

static void loescheDuplikate(IntList xl){
IntList list = xl;
IntList res = xl;
xl = xl.tail;
while(xl.tail != null){
if(res.head == xl.head){
res.tail = res.tail.tail;
xl = xl.tail.tail;
}
else{
res =res.tail;
xl = xl.tail;
}
}
}
News:
05.03.2015
2 Antworten
0
Erstmals must du die bestehende Liste als Ergebnis geben, und nicht ein void. Du kannst diese Losung versuchen.

public static int[] loescheDuplikate(int []s){
int ergebnis[] = new int[s.length], j=0;
for (int i : s) {
if(!istVorhanden(ergebnis, i))
ergebnis[j++] = i;
}
return ergebnis;
}
private static boolean istVorhanden(int[] array, int value){
for (int i : array) {
if(i==value)
return true;
}
return false;
}
06.03.2015
radulemnaru 31 1
0
Aufgabenstellung:

  • aufsteigendend sortierten Liste
  • die bestehende Liste soll verändert werden
  • der Algorithmus soll in linearer Zeit arbeiten.

Lösung:
public static void loescheDublikate(final ArrayList<Integer> list) {
int last = list.get(0);
int i = 0;
while (i < list.size()) {
if (list.get(i) == last) {
list.remove(i); // löschen wenn aktuelles element == vorheriges element
} else {
last = list.get(i);
i++;
}
}
}


Der Algorithmus verändert die bestehende Liste und ist linear (O(n)). Er funktioniert aber nur wenn die Liste bereits sortiert ist.

[Edit: Tippfehler]
06.03.2015
phg 1,6k 3

Stelle deine Java-Frage jetzt!