Größte nicht doppelte Zahl aus Array suchen

mcdonor

Hey Leute,

ich suche nach einer Möglichkeit mit der ich in einem Array die größte und nicht doppelte Zahl suchen kann.

Also ich habe z.B.:

Int Zahl[10];

Zahl {3,4,5,6,7,8,9,10,11,11}

Dann wäre die gesuchte Zahl ja 10 sein.
Ich bin blutiger Anfänger und mir fällt da keine Möglichkeit ein.
Vielen Dank im voraus.

Wenn die so schön aufsteigend sortiert sind, sollte das doch einfach sein.
Zeig mal das du dir Gedanken machst

Also Quelltext anfangen und eine Zahl nach der anderen auslesen.

Los hau rein und lass uns mal ein wenig Quelltext sehen.

MfG f.-th.

mcdonor

Bevor ich anfange... Da gibt es doch iwie eine Funktion für, qsort() oder so? Also könnte ich doch einfach qsort(Zahlen) oder so schreiben?

Wutz

Ja.

Binggi

void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );

alogheo

Aber wenn du ein "blutiger Anfänger" bist solltest du trotzdem mal versuchen die funktion selber zu schreiben (einfach nur um etwas dazu zu lernen).

mcdonor

Also, ich hatte den Wikipedia Artikel und einige andere Foreneinträge zu der Quicksort-Funktion mir angeguckt. So in etwa habe ich jetzt verstanden wie mit dem Algorithmus, der da hinter steht, die Variablen sortiert werden. Was ich nicht verstehe ist was ich in der Funktion angeben muss.

qsort(Array, Anzahl der Variablen im Array, und dann?)

Entschuldigt bitte wenn ich mich ein wenig ungeschickt ausdrücke.

man: qsort

void qsort(void *base, size_t nmemb, size_t size,
                int(*compar)(const void *, const void *));

base: Zeiger auf das erste Element des zu sortierenden Bereichs
nmemb: Anzahl der zu sortierenden Elemente
size: Größe eines dieser Elemente in bytes
compar: Die Vergleichsfunktion. Eigentlich das einzige wo es etwas komplizierter wird. Diese Funktion musst du selbst schreiben, damit qsort() weiss wie die Elemente sortiert werden sollen. Im wesentlichen sagst du in der Funktion, welche der Elemtente größer/kleiner/gleich sind. Hinweis: mit qsort kannst du so ziemlich alles sortieren, solange die Elemente hintereinander im SPeicher liegen, also auch Strukturen oder sonstiges.
Diese Funktion soll folgende Signatur haben:

int compar (const void *a, const void *a);

a und b sind Zeiger auf die aktuell zu vergleichenden Elemente. Mit ein bißchen rumgecaste und Dereferenzierung bekommst du dann die eigentlichen Werte x und y:

int x, y;
x = *((const int *)a);
y = *((const int *)b);

Die Vergleichsfunktion soll, wie auch in der manpage steht, etwas kleiner, gleich oder größer 0 zurückgeben.

if (x<y)
    return -1;
else if (x>y)
    return 1;
else
    return 0;

Damit sollte qsort() verständlicher sein.

mcdonor

Ja, vielen Dank, das hilft sehr.
Wenn man, wie du sagst, so ziemlich alles mit Quicksort sortieren kann, wird es wohl noch sehr wertvoll für mich werden...
Danke allen nochmal

mcdonor schrieb:

So in etwa habe ich jetzt verstanden wie mit dem Algorithmus, der da hinter steht, die Variablen sortiert werden.

Das ist schon eine ganze Menge. Quicksort ist nicht unbedingt die einfachste aller Sortiermethoden (obwohl es rekursiv auch nicht sonderlich komplex ist), einfacher zu verstehen finde ich Selectionsort.

Genauso naiv würde ich auch vorgehen um dein Problem zu lösen, du suchst erst die grösste Zahl und überprüfst, ob sie nochmal vorkommt. Wenn nicht, nimmst du sie als obere Marke und suchst du die grösste Zahl, die kleiner ist als diese Marke. Falls diese Zahl auch mehrfach vorkommt, wiederholst du das Verfahren.
Laufzeittechnisch ist es so nicht ganz optimal (im schlechtesten Fall O(n²)), aber dann ist auch qsort nicht ideal (O(n²)), so dass du eine andere Sortiermethode verwenden musst. Die schnellste Lösung wäre in O(n) machbar.