Arrays doppelte einträge eliminieren

[qwertz543221]

hallo

habe wie folgt versucht, ein array aus randomzahlen (oder vordefiniert) so zu bearbeiten, dass in der ausgabe nur noch jede vorkommende zahl nur noch einmal auftaucht. (... wunschvorstellung)

leider ist es mir nicht gelungen, alle überflüssiigen zu entfernen.
meine idee war folgende:
1 - (aufsteigendes) sortieren des arrays
2 - danach von vorn bis hinten mit einem zähler durchlaufen und schauen, ob einträge doppelt sind
3 - diese einträge dann nach hinten verschieben (damit sich die größe nicht ändert, dachte ich, man könnte einfach diese mit den letzten einträgen tauschen)
dabei wird die anzahl der vertauschungen mitgezählt
4 - so viele einträge hinten abschneiden (setlength), wie der zähler angibt
5 - da das array jetzz wieder unsortiert ist, noch einmal sortieren.


soviel zur idee, bei der ausführung hakt es jedoch, weiß jedoch nicht woran....


qt siehe unten

Delphi-Quellcode:

var i,j,x:longint;

begin

i:=0;
j:=-1;
i:=0;

quicksort(test1,low(test1),high(test1));

while i< = length(test1) do
begin
if test1[i] = test1[i+1] //doppelt?
  then
    begin
    {ans ende stellen durch tauschen}
    x:=test1[i];
    test1[i]:=test1[length(test1)-1]; //möglicherweise ist hier ein fehler???
    test1[length(test1)-1]:=x;
    j:=j+1;
    end;
i:=i+1;
end;

setlength(test1,length(test1)-j);
quicksort(test1,low(test1),high(test1));
write(test1); //ausgabe
end;

vielen dank für eure tips

[alzaimar]

Delphi-Quellcode:

j := 0;
i := 1;
while i < Length (MyArray) - 1 do begin
  if MyArray[i] <> MyArray[j] then begin 
    MyArray[j] := MyArray[i];
    inc(j);
    SetLength (MyArray, Length (MyArray) - 1);
  end;
  inc(i);
end;

Getippt und nicht getestet.

[Corpsman]

Also ich bin ja der meineung das dein 2. Sortieren nicht notwendig ist.

Denn du entfernst aus einem Sortierten Array alle Doppelten, wo soll da Unordnung entstehen ?


Probier mal das hier, ..

Delphi-Quellcode:

  quicksort_Array;
  // entfernen doppelte, dreifache ..
  for i :=high(MyArray) downto 1 do begin
    if MyArray[i-1] = MyArray[i] then begin
      for j := i to High(Myarray)-1 do begin
      myArray[j] := myArray[j+1]; 
      end;
      setlength(Myarray, high(myarray));
    end;
  end;

habs aber nicht getestet ,)

[alzaimar]

Corpsman, deine Lösung ist vom Aufwand O(n^2), meine nur O(n).

[himitsu]

Falls nicht sortiert werden soll/muß

Delphi-Quellcode:

j := 0;
for i := 0 to High(MyArray) do begin
  k := High(MyArray);
  while k > i do 
    if MyArray[i] = MyArray[k] then break else Dec(k);
  if k <> i then Continue;
  MyArray[j] := MyArray[k];
  Inc(j);
end;
SetLength(MyArray, j);

Insgesamt isses eh etwas besser, wenn man nicht ständig das Array (Länge/Speicherverwaltung) ändert.


[add]
meines ist dann wohl irgendwas zwischen O(n^2) und O(n), aber dafür entfällt das vorhergehende Sortieren, welches auch irgendwas über O(n) ist

meines: O(n)..O(n^2)
alzaimar: O(n) + O(n)..O(n^2)
Corpsman: O(n^2) + O(n)..O(n^2)

(die Zeit für eure vielen SetLength hab ich ignoriert)

[alzaimar]

Das ist -mit Verlaub- falsch.

Mein Algorithmus ist O(n) und nicht O(n^2). Auch nicht irgendwas dazwischen. Wir haben eine einfache Schleife über alle Arrayelemente.
Dein Algorithmus ist O(n^2), da es sich um zwei verschachtelte Schleifen mit einer Schleifenlänge proportional N (Anzahl der Arrayelemente) handelt.

Wenn man das Sortieren hinzuzählt, dann ist mein Algorithmus O(n log n). (Komplexität eines beliebigen guten allgemeinen Sortierverfahrens). Wenn Radixsort erlaubt wäre, blieben wir bei O(n).

Bei kombinierten Algorithmen wird die Komplexität des ...komplexeren... Algorithmus genommen.

Komplexitäten kann man im Übrigen nicht addieren.

[gammatester]

Zitat:

Zitat von alzaimar

Das ist -mit Verlaub- falsch.

Mein Algorithmus ist O(n) und nicht O(n^2). Auch nicht irgendwas dazwischen. Wir haben eine einfache Schleife über alle Arrayelemente.

Dafür ist er allerdings -mit Verlaub- völliger Schrott: Wenn man Deinen Code wirklich mal testet, ergibt sich zB

(1,1,2) -> (1,1,2) oder (1,2,1) -> (2,2)

Was sollen also die ganzen Komplexitätsüberlegungen? Das wichtigste ist ein Algorithmus, das tut was er soll.

Gruß Gammatester

[jfheins]

Wenn die Zahlen nicht allzu groß sind, würde ich einen (leicht modifizierten) Bucketsort empfehlen ...

[qwertz543221]

corpsman:

Zitat:

Probier mal das hier, ..
[delphi]
// quicksort_Array;
// entfernen doppelte, dreifache ..
for i :=high(MyArray) downto 1 do begin
if MyArray[i-1] = MyArray[i] then begin
for j := i to High(Myarray)-1 do begin
myArray[j] := myArray[j+1];
end;
setlength(Myarray, high(myarray));
end;
end;
[delphi]


habs aber nicht getestet ,)

danke - das ist in kürze das ausgesagt, was ich brauchte. danke auch an alle anderen für ihre bemühungen.

[alzaimar]

Zitat:

Zitat von gammatester

Dafür ist er allerdings -mit Verlaub- völliger Schrott:

Sehr erfreut, Ihren Charakter kennenzulernen.

Zitat:

... (1,2,1) -> (2,2)

Sortiert sollte die Liste schon sein, so wie in der Lösung des Threaderstellers erwähnt.

Allerdings hast Du bezüglich er mangelnden Korrektheit Recht. Da hat sich -da ungetestet- ein kleiner Fehler eingeschlichen. Danke für's testen. Hier der korrekte Code: Er ist sogar etwas einfacher:

Delphi-Quellcode:

  // MyArray ist sortiert.

  j := 0;
  i := 1;
  while i <= Length (myArray) - 1 do
    if MyArray[i] <> MyArray[j] then begin
      inc(j);
      MyArray[j] := MyArray[i];
    end
    else
      inc(i);

  SetLength (myArray,j+1);

Zitat:

Was sollen also die ganzen Komplexitätsüberlegungen? Das wichtigste ist ein Algorithmus, das tut was er soll.

So kann man das auch sehen.

Es gibt Leute, die wollen nicht nur eine Lösung, sondern sind bestrebt, eine optimale Lösung zu finden. Du gehörst offensichtlich nicht dazu, sondern eher zu dem Schlag, der stattdessen lieber rumpöbelt. Bitte sehr. Jedem das Seine. Oder bist Du nur mit dem falschen Fuß aufgestanden