Füllung einer Zahlenliste

[egal]

Sorry für den blöden Titel, aber was besseres fällt mir nicht ein.
Ich hab ein folgendes Problem: ich habe eine sortierte Liste mit Zahlen, z.B. 1,2,5,100,203,999, bis 999. In diese Liste muss ich neue Zahlen schreiben. Wenn diese Zahl gibt's in dieser Liste nicht, dann schreibe ich sie einfach rein und sortiere. Aber wenn diese Zahl schon vergeben ist, z.B. 100, dann muss ich meine Zahl auf kleinere noch nicht besetzte Zahl in der Liste ändern, in meinem Beispiel ist es Zahl 3.
Und jetzt die Frage, wie kann ich diese kleinere noch nicht besetzte Zahl schnell finden? Ich habe ein Paar Gedanken, aber das ist alles total langsam.
Danke.

[leddl]

Mir fällt spontan nur ein, die Listbox von vorne durchzugehen und zu prüfen, ob die Zahl am entsprechenden Index Index+1 ist. Ist das nicht der Fall, kannst du Index + 1 einfügen. (Vorausgesetzt, du startest mit 1, und nicht mit 0)
Also:

Delphi-Quellcode:

For i := 0 To ListBox1.Items.Count - 1 Do
  If StrToInt(ListBox1.Items[i]) > i+1 Then
    break;
//i+1 ist die Zahl, die eingefügt werden muß
//i ist der Index, bei dem eingefügt werden muß

Sollte aber auch so funktionieren.

Delphi-Quellcode:

i := 0;
While (i <= ListBox1.Items.Count - 1) and (StrToInt(ListBox1.Items[i]) = i+1) Do
  inc(i);
//i ist die Zahl, die eingefügt werden muß
//i-1 ist der Index, bei dem eingefügt werden muß

Ist aber jetzt alles nur aus dem Kopf schludrig hingeschrieben und kann noch Denkfehler beinhalten.

//Diverse Edits
Kleinere Schreibfehler gefixt und Kleinigkeiten eingefügt

[Sharky]

Zitat von egal:

... dann muss ich meine Zahl auf kleinere noch nicht besetzte Zahl in der Liste ändern, in meinem Beispiel ist es Zahl 3.

Hai egal,
wenn ich das richtig lese musst Du nicht die kleinere sondern die kleinste nicht "besetzte" Zahl einfügen oder?

[egal]

Zitat von Sharky:

Zitat von egal:

... dann muss ich meine Zahl auf kleinere noch nicht besetzte Zahl in der Liste ändern, in meinem Beispiel ist es Zahl 3.

Hai egal,
wenn ich das richtig lese musst Du nicht die kleinere sondern die kleinste nicht "besetzte" Zahl einfügen oder?

jo, hast du Recht

[leddl]

OK, aber meine Antwort wird ignoriert...

[Sharky]

Zitat von leddl:

OK, aber meine Antwort wird ignoriert...

Hai leddl,
irgendwie erkenne ich bei deinem Code nicht was er zur Lösung des Problemes bringen soll

@egal:
Wo ist denn das Hauptproblem? Bei herausfinden ob eine Zahl schon in deiner sortierten Liste (wie ist diese eigentlich aufgebaut) vorhanden ist oder beim bestimmen der kleinsten nicht vorhandenen Zahl?

[egal]

Zitat von leddl:

Mir fällt spontan nur ein, die Listbox von vorne durchzugehen und zu prüfen, ob die Zahl am entsprechenden Index Index+1 ist. Ist das nicht der Fall, kannst du Index + 1 einfügen. (Vorausgesetzt, du startest mit 1, und nicht mit 0)
Also:

Delphi-Quellcode:

For i := 0 To ListBox1.Items.Count Do
  If StrToInt(ListBox1.Items[i]) > i+1 Then
    break;
//i+1 ist die Zahl, die eingefügt werden muß
//i ist der Index, bei dem eingefügt werden muß

Sollte aber auch so funktionieren.

Delphi-Quellcode:

i := 0;
While (i <= ListBox1.Items.Count - 1) and (StrToInt(ListBox1.Items[i]) = i+1) Do
  inc(i);
//i ist die Zahl, die eingefügt werden muß
//i-1 ist der Index, bei dem eingefügt werden muß

Ist aber jetzt alles nur aus dem Kopf schludrig hingeschrieben und kann noch Denkfehler beinhalten.

Danke, kannst du mir auch sagen, welche Lösung schneller ist? Da brauche ich jede Mikrosekunde

[leddl]

Zitat von Sharky:

Hai leddl,
irgendwie erkenne ich bei deinem Code nicht was er zur Lösung des Problemes bringen soll

Wie bitte? Er wollte wissen, wie er an die erste nicht besetzte Zahl kommt, und genau das machen doch die beiden Codeschnipsel. Da die Listbox sortiert ist, kann man von vorne aus prüfen, welche Zahlen vorhanden sind. Man fängt also beim ersten Item (Index = 0) an und prüft, ob der Wert dort 1 ist. Was kleineres als 1 kann da nicht stehen, also ist es entweder 1 oder größer als 1. Steht eine 1, muß das nächste Item geprüft werden. Steht keine 1, hat man seine gesuchte Zahl und den Index (der natürlich immer "einzufügende Zahl -1" ist)
Inwiefern löst das das Problem nicht?

Zitat von egal:

Danke, kannst du mir auch sagen, welche Lösung schneller ist? Da brauche ich jede Mikrosekunde

Testen... Ich hab hier kein Delphi um es für dich zu machen. Aber laut meinem Verständnis sollte es ziemlich gleich schnell sein, da ja eigentlich bei beiden Varianten genau das selbe passiert.

//Edit:
Aber ganz wichtig: Die For-Schleife muß bis ListBox1.Items.Count - 1 gehen. Das is mit durchgerutscht!

[egal]

Zitat von Sharky:

Zitat von leddl:

OK, aber meine Antwort wird ignoriert...

Hai leddl,
irgendwie erkenne ich bei deinem Code nicht was er zur Lösung des Problemes bringen soll

@egal:
Wo ist denn das Hauptproblem? Bei herausfinden ob eine Zahl schon in deiner sortierten Liste (wie ist diese eigentlich aufgebaut) vorhanden ist oder beim bestimmen der kleinsten nicht vorhandenen Zahl?

Das Problem ist, wie finde ich die kleinste nicht vorhandene Zahl. Wie ist die Liste aufgebaut, es hängt von mir ab. Das kann eine ListBox oder ein Array sein. Die Liste ist sortiert.

[leddl]

Also sofern ich dein Problem wirklich richtig verstanden habe (Sharky macht mich da ganz wuschig ), sollte mein Code es absolut tun. Besonders viel schneller sollte es auch eigentlich nicht gehen, denn du hast ja nur 2 Möglichkeiten:

• Entweder, du prüfst jede Zahl von 1 bis 999 durch, ob sie vorhanden ist (das kann dann aber etwas länger dauern, da du bei einer ListBox dafür IndexOf aufrufen müsstest, das aber für jede Zahl [bis eine nicht vorhanden ist] alle Items bis zur gesuchten Zahl durchgehen müsste, und das kann sich ja summieren)
• oder du gehst ein Item nach dem anderen durch und prüfst, ob noch eine Zahl reinpasst. Und das sollte die deutlich schnellere Variante sein. Und genau das macht doch mein Code. Wenn die Liste sortiert ist und es keine Lücken gibt, muß doch jedes Element mit dem Index i den Wert i+1 (ListBox ist 0-basiert, bei 1-basiertem Array wäre es natürlich i) besitzen. Kleiner als i kann der Wert nicht sein, da wir ja mit natürlichen Zahlen rechnen. Ist der Wert am Index i größer als i+1 haben wir ne Lücke und damit die gesuchte Zahl. Voilá!

Bei einem Array müsstest du in meinem Code eben einige kleinere Änderungen machen (zB. "ListBox1.Items.Count - 1" gegen "Length(MyArray) - 1" austauschen).