algo um doppelte zahlen zu finden ?

hi, ich habe ein dynamisch allokiertes array von unsigned long zahlen.
jetzt würde ich gerne auf doppelte/dreifache usw checken, wie mach ich das am besten ? thx

gibbets2000

kann man das nicht in etwa so machen?

unsigned long temp;
for(int i = 0; i < ArrayGröße; i++)
{
temp = Array[i];
for(int j = i + 1; j < AttayGröße; j++)
{
if(temp == Array[j])
//Übereinstimmung
}
}

hab das aber nicht getestet...

Phillemann

Was willst du denn dann mit den mehrfach vorkommenden machen? Aus dem Array Löschen?

volkard

Phillemann schrieb:

Was willst du denn dann mit den mehrfach vorkommenden machen? Aus dem Array Löschen?

direktes absuchen kostet O(n^2) zeit bei n elementen. man kann das feld gerne vorher in O(n*log(n)) sortieren und dann einmal von unten nach oben durchgehen, und dabei nur die benachbarten auf gleichheit testen.

@gibbets2000
ja aber wenn eine zahl 3mal vorkommt dann kommt zuerst
zahl a ist gleich b und c und dann noch zahl b ist gleich c
will aber nur einmal die doppelten angezeigt bekommen

@volker und wie mach ich das ?

volkard

//ungetestet
int lasti=0;
for(int i=1;i<anz;++i)
   if(a[i]==a[lasti])
      tunix();
   else
   {
      print(a[i]);
      lasti=i;
   }

edit: fehler, wenn a[1]==a[0]. ist evtl besser, werte zu speichern. wirst es schon hinkriegen.

kann ich es mit quicksort sortieren und dann checken ?

brain-death

noi schrieb:

kann ich es mit quicksort sortieren und dann checken ?

ja! aber was soll das bringen?

mady

paranoiac.org schrieb:

noi schrieb:

kann ich es mit quicksort sortieren und dann checken ?

ja! aber was soll das bringen?

Wenn die Zahlen sortiert sind, kann man einfacher (schneller) doppelte Einträge finden, weil diese ja 'zusammenstehen'.

brain-death

mady schrieb:

paranoiac.org schrieb:

noi schrieb:

kann ich es mit quicksort sortieren und dann checken ?

ja! aber was soll das bringen?

Wenn die Zahlen sortiert sind, kann man einfacher (schneller) doppelte Einträge finden, weil diese ja 'zusammenstehen'.

In dem Fall durchläuft er aber die Schleife sowieso!
Also ist es dochj eigentlich egal.

volkard

noi schrieb:

kann ich es mit quicksort sortieren und dann checken ?

ja, und das sollte man auch. evtl heapsort oder shellsort nehmen, wenn die datenlage mit quicksort nicht glücklich verheiratet werden kann.