(C'est une généralisation de votre idée pour les deux tableaux).
Si vous commencez par regarder la cinq médianes des cinq tableaux, évidemment, la médiane globale doit être entre le plus petit et le plus grand des cinq médianes.
La preuve va quelque chose comme ceci: Si a est le min des médianes, et b est le max de la médianes, puis chaque tableau est moins de la moitié de ses éléments moins d'un et moins de la moitié de ses éléments supérieur à b. Résultat suit.
Ainsi, dans le tableau contenant un, jeter les numéros de moins de un; dans le tableau contenant b, jeter les nombres plus grand que b... Mais seulement jeter le même nombre d'éléments des deux tableaux.
C'est, si a est j éléments à partir du début de son éventail, et b à k éléments à partir de la fin de son tableau, vous jetez le premier min(j,k) les éléments d'un tableau et la dernière min(j,k) d'éléments de b du tableau.
Itérer jusqu'à ce que vous êtes jusqu'à 1 ou 2 éléments total.
Chacune de ces opérations (c'est à dire, trouver la médiane d'un tableau trié et jeter k éléments à partir du début ou de la fin d'un tableau) est la constante de temps. Donc à chaque itération est la constante de temps.
Chaque itération jette (plus de) la moitié des éléments à partir d'au moins une matrice, et vous ne pouvez le faire que log(n) fois pour chacun des cinq tableaux... de Sorte que l'ensemble de l'algorithme est log(n).
[Mise à jour]
Comme Himadri Choudhury points dans les commentaires, ma solution est incomplète; il y a beaucoup de détails et le coin des cas, à s'inquiéter. Donc, à la chair des choses un peu...
Pour chacun des cinq tableaux de R, la définition de ses médian inférieur" R[n/2-1] et de son "supérieur" médiane de R[n/2], où n est le nombre d'éléments dans le tableau (et les tableaux sont indexés à partir de 0, et la division par 2 arrondi vers le bas).
Laissez "un" être le plus petit de la basse-terre-pleins, et "b" être le plus important de la partie supérieure du médianes. S'il y a plusieurs tableaux avec la plus petite inférieur à la médiane et/ou plusieurs tableaux ayant le plus haut revenu médian, choisir a et b à partir de différentes matrices (c'est un de ces cas de coin).
Maintenant, l'emprunt Himadri suggestion: Effacer tous les éléments jusqu'à et y compris un à partir de son tableau, et tous les éléments vers le bas à et y compris b à partir de son tableau, en prenant soin d'enlever le même nombre d'éléments des deux tableaux. Noter que a et b pourraient être dans le même tableau; mais, dans ce cas, ils ne pourraient pas avoir la même valeur, parce que sinon, on aurait été en mesure de choisir l'un d'entre eux à partir d'un tableau différent. Donc c'est OK si cette étape des vents jusqu'à jeter des éléments à partir du début et de la fin de la même matrice.
Itérer tant que vous avez trois ou plusieurs tableaux. Mais une fois que vous êtes vers le bas, juste un ou deux tableaux, vous devez modifier votre stratégie pour être exclusif au lieu de inclusivement; vous n'efface jusqu'à , mais pas y compris l' un et en bas à mais pas y compris b. Continuer comme ça, en autant que le reste de un ou deux tableaux a au moins trois éléments (en vous garantissant faire des progrès).
Enfin, vous permettra de réduire de quelques cas, la plus délicate, qui est de deux tableaux restants, dont l'un a un ou deux éléments. Maintenant, si je vous ai demandé: "étant Donné un tableau trié plus un ou deux éléments supplémentaires, la médiane de tous les éléments", je pense que vous pouvez le faire en temps constant. (Encore une fois, il y a un tas de détails à peaufiner, mais l'idée de base est que l'ajout d'un ou deux éléments d'un tableau ne pas "pousser la médiane autour de" beaucoup.)
