Arrays doppelte einträge eliminieren

[gammatester]

Zitat von alzaimar:

Danke für's testen. Hier der korrekte Code:

Wollte gerade etwas ausführlicher antworten, als Deine PN auftauchte. Mehr dort, hier nur kurz: Der verbesserte Code ist allerdings entgegen Deiner Behauptung immer noch nicht korrekt, zB wird ein Feld der Länge 0 auf Länge 1 gesetzt.

[user0815]

Frage: Kann man nicht auch einfach eine Stringlist nehmen mit folgenden Eigenschaften: Sorted := True sowie Duplicates := dupIgnore ?

[gammatester]

Zitat von user0815:

Frage: Kann man nicht auch einfach eine Stringlist nehmen mit folgenden Eigenschaften: Sorted := True sowie Duplicates := dupIgnore ?

Das wäre allerdings ziemlich umständlich, da die Zahlen erst in Strings umgewandelt, in die Liste verfrachtet, und anschließend wieder zu Zahlen gemacht werden müssen. Da wir nicht wissen, was der TE unter Random-Zahlen versteht, besteht dabei für zumindest für random()-Zahlen (d.h. Fließkommazahlen zwischen 0 und 1) die Gefahr von Umwandlungsungenauigkeiten mit Folgefehlern.

[qwertz543221]

wie ganz zu bewginn erwähnt (nur kurz in der klammerangabe), müssen es nicht nur randomzahlen sein, sondern es dürfen auch zb vordenfinierte arrays - später sollen daraus verkettete listen aus records (eintrag+zeiger auf nächstes element) werden - bearbeitet werden.

Die Randomzahlen stellen nur den anfang dar, um das ganze ienmal zum laufen zu bringen, bzw mögliche vorgehensweisen zu erproben oder zu verfeinern, dafür habt ihr mir ja schon eineiges an nfomaterial geliefert.

[Blup]

Eine Möglichkeit wäre das Sortieren mit dem Filtern zu koppeln:

Delphi-Quellcode:

type
  TElement = Integer;
  TMyArray = array of TElement;

function Filter(const Arr: TMyArray): TMyArray;
{---}
  function MyCompare(const Item1, Item2: TElement): Integer; inline;
  begin
    {Vergleich abhängig vom Typ der Elemente}
    Result := Item1 - Item2;
  end;
{---}
  procedure AddResult(var Result: TMyArray; const Element: TElement); inline;
  var
    idx, idx1, idx2, iComp: Integer;
  begin
    {Index finden}
    idx1 := 0;
    idx2 := High(Result);
    while idx1 <= idx2 do
    begin
      idx := (idx1 + idx2) div 2;
      iComp := MyCompare(Result[idx], Element);
      if iComp < 0 then
        idx1 := idx + 1
      else if iComp > 0 then
        idx2 := idx - 1
      else
        Exit;
    end;
    {Einfügen}
    SetLength(Result, Length(Result) + 1);
    for idx := High(Result) downto idx1 + 1 do
    begin
      Result[idx] := Result[idx - 1];
    end;
    Result[idx1] := Element;
  end;
{---}
var
  i: Integer;
begin
  for i := 0 to High(Arr) do
    AddResult(Result, Arr[i]);
end;

[Codix32]

Hier meine zusammengeschusterte Routine. Die funktioniert perfekt:

Delphi-Quellcode:

Type
 TSXArray = array of shortint;

...
...
var
 SXArray:TSXArray;
....
....
procedure TForm1.entfernedoppelteWerte(myarray:TSXARRAY);
var
  i:integer;
begin
 for i :=high(MyArray) downto 0 do
  begin
   if MyArray[i-1] = MyArray[i] then
      loescheArray(SXArray,i);
  end;

procedure TForm1.loescheArray(var A:TSXArray;Aindex:Integer);
begin
   Move(A[AIndex + 1], A[AIndex], SizeOf(A[0]) * (Length(A) - AIndex - 1));
   SetLength(A, Length(A) - 1); // Länge kürzen
end;

Die Routine geht mit oder ohne Sortierung.

[BUG]

Ich fände es interessant, dass Ganze als modifizierten Mergesort zu implementieren und bei jedem Merge die Dopplungen zu eliminieren. Bei vielen beieinander liegenden Dopplungen könnte das vielleicht sogar ganz vernünftig sein.

[Bjoerk]

Hatte letztens exakt das gleiche Problem. Den Code auf eine IntegerList übertragen:

Delphi-Quellcode:

procedure TIntegerList.RemoveDoubles;
var
  I, J, NewCount: integer;
begin
  if Count > 1 then // Count = Length(Items);
  begin
    Sort;
    I := 0;
    NewCount := 0;
    while I < Count do
    begin
      J := I;
      while (J < Count - 1) and (Items[I] = Items[J + 1]) do
        Inc(J);
      Items[NewCount] := Items[I];
      Inc(NewCount);
      I := J + 1;
    end;
    Count := NewCount; // SetLength(Items, NewCount);
  end;
end;

[Namenloser]

Eine Hashmap wäre auch noch eine Möglichkeit. Einfach im ersten Schritt alle Elemente des einen Arrays durchlaufen und in die Map einfügen, dann im zweiten Schritt das zweite Array durchlaufen und prüfen, ob das jeweilige Element in der Hashmap ist. Wäre dann O(n) für alles zusammen. Ist dafür nicht in-place.

[Dejan Vu]

Hatte ich auch vorgeschlagen, aber der TE hatte sich nicht an diese Struktur 'herangetraut' (soweit ich mich erinnere).
Zudem müsste man die Punkte rastern (weil nicht auf Gleichheit, sondern auf Nähe verglichen wird), und das gäbe ein 'falsches' Ergebnis. Nun muss man dazu sagen, das die jetzige Lösung (Sortieren und Eliminieren) auch 'falsch' ist, bzw. nicht optimal bezüglich der Anzahl der übrig gebliebenen Punkte.