AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Programmieren allgemein Arrays doppelte einträge eliminieren

Arrays doppelte einträge eliminieren

Ein Thema von qwertz543221 · begonnen am 15. Dez 2009 · letzter Beitrag vom 22. Dez 2014
Antwort Antwort
Seite 1 von 3  1 23   
qwertz543221
(Gast)

n/a Beiträge
 
#1

Arrays doppelte einträge eliminieren

  Alt 15. Dez 2009, 00:05
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
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#2

Re: Arrays doppelte einträge eliminieren

  Alt 15. Dez 2009, 06:51
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.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Benutzerbild von Corpsman
Corpsman

Registriert seit: 8. Nov 2005
Ort: nähe Stuttgart
981 Beiträge
 
Delphi XE2 Professional
 
#3

Re: Arrays doppelte einträge eliminieren

  Alt 15. Dez 2009, 07:47
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 ,)
Uwe
My Sitewww.Corpsman.de

My marble madness clone Balanced ( ca. 70,0 mb ) aktuell ver 2.01
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#4

Re: Arrays doppelte einträge eliminieren

  Alt 15. Dez 2009, 07:54
Corpsman, deine Lösung ist vom Aufwand O(n^2), meine nur O(n).
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
43.017 Beiträge
 
Delphi 12 Athens
 
#5

Re: Arrays doppelte einträge eliminieren

  Alt 15. Dez 2009, 08:02
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)
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list : BugReports/FeatureRequests
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#6

Re: Arrays doppelte einträge eliminieren

  Alt 15. Dez 2009, 08:28
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.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
gammatester

Registriert seit: 6. Dez 2005
999 Beiträge
 
#7

Re: Arrays doppelte einträge eliminieren

  Alt 15. Dez 2009, 09:11
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
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.579 Beiträge
 
#8

Re: Arrays doppelte einträge eliminieren

  Alt 15. Dez 2009, 09:43
Wenn die Zahlen nicht allzu groß sind, würde ich einen (leicht modifizierten) Bucketsort empfehlen ...
  Mit Zitat antworten Zitat
qwertz543221
(Gast)

n/a Beiträge
 
#9

Re: Arrays doppelte einträge eliminieren

  Alt 15. Dez 2009, 16:57
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.
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#10

Re: Arrays doppelte einträge eliminieren

  Alt 15. Dez 2009, 21:13
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
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 3  1 23   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 03:24 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz