Gegeben seien 2 aufsteigende Arrays X[a..b] und Y[c..d], wobei alle Arrayelemente paarweise verschieden sind. Weiter ist eine Zahl k <= (b - a) + (d - c) gegeben.

Entwickel einen Algorithmus, der die k-größte Zahl in X und Y in Zeit O(log((b - a) + (d - c))) findet.

Viel Spass! :)

da musste aber noch nen preis ausschreiben ;)

wenn du das jetzt noch so formulierst, dass die von uns, die nicht studiert haben, das auch verstehen, dann überleg ich mir evtl. 'ne lösung

also
man hat zwei arrays, z.B.
X = [1,2,3,4] (oder X=[1,9,20,999])
Y = [2,3,4,5] (oder Y=[12,43,97,98])

nun hat man folgenedes:
a = 1, b = 4 (bzw. a=1, b=999)
c = 2, d = 5 (bzw. c=12, d=98 )

k lässt sich berechnen wie folgt:

k <= (b - a) + (d - c)
k <= (4 - 1) + (5 - 2) (oder (999-1) + (98 - 12))
k <= 6 (oder 1084)

k <= heißt, dass wenn das Array nicht k Einträge hat, man k soverkleinern muss, dass k = Größe des Arrays wird...

die k-größte Zahl mit k = 3 aus X = [1,2,3,4] ist dann 2\n\n

<!--EDIT|esskar|1118938618-->

ei verbibsch etzertla funktioniert mein ausgedachter algo nicht :(

[quote=kabel,16.06.2005, 20:55]ei verbibsch etzertla funktioniert mein ausgedachter algo nicht :([/quote]
ich versteh dich zwar nicht, aber ich kam auch nicht drauf!

Nur so ein paar Gedanken: Da die Arrays streng monoton steigend angeordnet sind, muss man zum finden des k-größten Elements nur beide Arrays von hinten durchgehen und sich dabei die Reihenfolge merken. Das macht man, bis man auf das k-größte Element gestoßen ist.

Ob das dann der Komplexitätsanforderung genügt, weiß ich nicht, aber es scheint mir recht "schnell" zu sein :-D\n\n

<!--EDIT|Crian|1119262071-->

hmm...
nicht wirklich...
wenn k == size ist, dann nicht.
es geht über einen baum...
lösung kommt demnächst!

Alternative: Man kann ein drittes Array aus den beiden zusammenbauen, das die Elemente beider Arrays monoton steigend enthält. Dann erfolgt die Ermittlung des k.-größten Elements in konstanter Zeit mittels $array[-$k]. Und das Array lässt sich für weitere Anfragen dieser Art wiederverwenden.\n\n

<!--EDIT|Crian|1119266472-->

[quote=Crian,20.06.2005, 13:19]$array[-$k][/quote]
wir sind zwar in einem perl forum, aber es war keine perl frage! :)