Bisher wurden ja nur verschiedene Implementierungen in linearer Zeit genannt.
Wir kennen aber folgende Eigenschaft: wenn eine Teilliste mit einer Zahl a beginnt und mit einer Zahl b endet, dann muss sie b - a + 1 Elemente enthalten. (Dies gilt natürlich nur, wenn man doppelte Elemente ausschließen kann)
Wir können also prüfen, ob ein Element im Array fehlt. Wenn das der Fall ist, machen wir das rekursiv für die erste und zweite Hälfte.
Wir wenden also einfach das bekannte Devide and Conquer-Prinzip auf unsere Eigenschaft dieser Listen an. Und schon lösen wir das Problem in logarithmischer Zeit.
Die Ausformulierung als Programm überlasse ich hier mal als Übungsaufgabe ;)
Es ist übrigens unwahrscheinlich, dass das Verfahren bei einer Hand voll (< 10 oder so) Elemente schon etwas bringt.
Interessant, auch wenn ich so etwas (noch) nicht hinbekommen würde.
Doppelte Elemente gibt es in der Liste nicht und je nach dem wie weit man schon in der Saison fortgeschritten ist können es 0 bis etwa 40 Spieltage sein, die im Array stecken.
Hi, na leider kann ich dir da nicht weiterhelfen.
Aber da du ja schon soooo viele Kommentare bekommenhast
ist das ja sicherlich nicht weiter schlimm :-(
Dennoch denke ich das bei dieser Vielzahl doch einige gute Ansätze dabei sind.
Beste Grüße
Mickey
da der Beitrag wohl schon ein bisschen älter ist, ist es wohl nicht mehr so richtig relevant, aber wenn du es, meiner Meinung nach, am performantesten haben möchtest solltest du es direkt in der DB machen.
SELECT id+1 FROM test WHERE (id+1) NOT IN (SELECT id FROM test) order by id LIMIT 1
Die Kommentare sind für diesen Eintrag geschlossen.
clynx schrieb am 19.09.2007
$x = 0; do { $x++; $y = array_shift( $matchdays); } while( $x == $y );Henryk Plötz schrieb am 19.09.2007
Daniel Thoma schrieb am 19.09.2007
Wir kennen aber folgende Eigenschaft: wenn eine Teilliste mit einer Zahl a beginnt und mit einer Zahl b endet, dann muss sie b - a + 1 Elemente enthalten. (Dies gilt natürlich nur, wenn man doppelte Elemente ausschließen kann)
Wir können also prüfen, ob ein Element im Array fehlt. Wenn das der Fall ist, machen wir das rekursiv für die erste und zweite Hälfte.
Wir wenden also einfach das bekannte Devide and Conquer-Prinzip auf unsere Eigenschaft dieser Listen an. Und schon lösen wir das Problem in logarithmischer Zeit.
Die Ausformulierung als Programm überlasse ich hier mal als Übungsaufgabe ;)
Es ist übrigens unwahrscheinlich, dass das Verfahren bei einer Hand voll (< 10 oder so) Elemente schon etwas bringt.
Jeena Paradies aus Varberg schrieb am 19.09.2007
Doppelte Elemente gibt es in der Liste nicht und je nach dem wie weit man schon in der Saison fortgeschritten ist können es 0 bis etwa 40 Spieltage sein, die im Array stecken.
Martin schrieb am 19.09.2007
Martin schrieb am 19.09.2007
Jeena Paradies aus Varberg schrieb am 19.09.2007
Daniel Thoma schrieb am 19.09.2007
dedlfix schrieb am 19.09.2007
zeek schrieb am 20.09.2007
Tim schrieb am 20.09.2007
Henryk Plötz schrieb am 20.09.2007
Tim schrieb am 20.09.2007
Martin schrieb am 20.09.2007
Jeena Paradies aus Varberg schrieb am 20.09.2007
zeek schrieb am 20.09.2007
Jeena Paradies aus Varberg schrieb am 20.09.2007
Martin schrieb am 20.09.2007
Mickey schrieb am 21.09.2007
Aber da du ja schon soooo viele Kommentare bekommenhast
ist das ja sicherlich nicht weiter schlimm :-(
Dennoch denke ich das bei dieser Vielzahl doch einige gute Ansätze dabei sind.
Beste Grüße
Mickey
Wolfgang aus Germany schrieb am 19.06.2008
da der Beitrag wohl schon ein bisschen älter ist, ist es wohl nicht mehr so richtig relevant, aber wenn du es, meiner Meinung nach, am performantesten haben möchtest solltest du es direkt in der DB machen.
SELECT id+1 FROM test WHERE (id+1) NOT IN (SELECT id FROM test) order by id LIMIT 1