Médiane de 5 tableaux triés

Question

J'essaie de trouver la solution pour la médiane de 5 tableaux triés. C'était une question d'entrevue. La solution à laquelle je pouvais penser était de fusionner les 5 réseaux puis de trouver la médiane [O (l + m + n + o + p)].

Je sais que pour 2 tableaux triés de même taille, nous pouvons le faire dans log (2n). [en comparant la médiane des deux tableaux puis en jetant 1 moitié de chaque tableau et en répétant le processus]. .. Trouver médian peut être le temps constant dans les tableaux triés .. donc je pense que ce n'est pas log (n)? .. quelle est la complexité du temps pour cela?

1] Existe-t-il une solution similaire pour 5 réseaux. Et si les tableaux sont de la même taille, y a-t-il une meilleure solution?

2] Je suppose que puisque cela a été demandé pour 5, il y aurait une solution pour N tableaux triés?

Merci pour les pointeurs.

des éclaircissements/questions que je demande de nouveau à l'intervieweur:
-ce que les tableaux de même longueur
=> Non
Je suppose qu'il y aurait un chevauchement dans les valeurs des tableaux
=> Oui

Comme un exercice, je pense que la logique pour 2 tableaux ne s'étend pas. Voici un essai:
En appliquant la logique ci-dessus de 2 tableaux pour dire 3 tableaux: [3,7,9] [4,8,15] [2,3,9] ... médians 7,8,3
éléments de projection [3,7,9] [4,8] [3,9] .. médians 7,6,6
éléments de projection [3,7] [8] [9] ..médias 5,8 , 9 ...
lancer des éléments [7] [8] [9] .. médiane = 8 ... Cela ne semble pas être correct?

La fusion d'éléments triés => [2,3,4,7,8,9,15] => prévu médiane = 7

Answer 1

(Ceci est une généralisation de votre idée de deux tableaux.)

Si vous commencez par regarder les cinq médianes des cinq réseaux, il est évident que la médiane globale doit être comprise entre la plus petite et la plus grande des cinq médianes. La preuve est quelque chose comme ceci: Si a est la min des médianes, et b est le maximum des médianes, alors chaque tableau a moins de la moitié de ses éléments moins de a et moins de la moitié de ses éléments plus grand que b. Le résultat suit. Donc dans le tableau contenant a, jetez les nombres inférieurs à a; dans le tableau contenant b, jetez les nombres supérieurs à b ... Mais jetez seulement le même nombre d'éléments des deux tableaux. Autrement dit, si a est j éléments depuis le début de son tableau, et b est k éléments de la fin de son tableau, vous jetez les premiers éléments min (j, k) de la matrice et la dernière min (j, k) éléments du tableau de b.

Itérer jusqu'à ce que le total soit égal à 1 ou 2 éléments. Chacune de ces opérations (c'est-à-dire, trouver la médiane d'une matrice triée et rejeter k éléments à partir du début ou de la fin d'une matrice) est une durée constante. Donc chaque itération est un temps constant.

Chaque itération jette (plus que) la moitié des éléments d'au moins un tableau, et vous ne pouvez faire que ce journal (n) fois pour chacun des cinq tableaux ... Donc l'algorithme global est log (n) .

[Mise à jour]

Comme Himadri Choudhury souligne dans les commentaires, ma solution est incomplète; Il y a beaucoup de détails et d'affaires à prendre en compte. Donc, pour étoffer les choses un peu ...

Pour chacun des cinq tableaux R, définissez sa "médiane inférieure" comme R [n/2-1] et sa "médiane supérieure" comme 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 arrondit à la baisse). Soit «a» la plus petite des médianes inférieures et «b» la plus grande des médianes supérieures. S'il existe plusieurs tableaux avec la plus petite médiane inférieure et/ou plusieurs tableaux avec la plus grande médiane supérieure, choisissez a et b à partir de tableaux différents (c'est l'un de ces cas-là).

Maintenant, emprunter la suggestion de Himadri: Effacer tous les éléments jusqu'à et y compris un de son tableau, et tous les éléments vers le bas à et notamment b de son tableau, en prenant soin d'enlever le même nombre d'éléments des deux tableaux . Notez que a et b pourraient être dans le même tableau; mais si c'est le cas, ils ne pourraient pas avoir la même valeur, sinon nous aurions pu en choisir un d'un tableau différent. Donc, c'est OK si cette étape finit par jeter des éléments du début et de la fin du même tableau.

Iterate tant que vous avez trois ou plusieurs groupes. Mais une fois que vous êtes à seulement un ou deux tableaux, vous devez changer votre stratégie pour être exclusive au lieu de inclusive; vous n'effacez que jusqu'à mais n'incluez pas a et mais n'incluez pas b. Continuez comme ça tant que les deux ou trois tableaux restants ont au moins trois éléments (vous garantissant des progrès). Enfin, vous réduirez à quelques cas, le plus difficile étant de deux tableaux restants, dont l'un a un ou deux éléments. Maintenant, si je vous demandais: "Étant donné un tableau trié plus un ou deux éléments supplémentaires, trouvez la médiane de tous les éléments", je pense que vous pouvez faire cela en temps constant. (Encore une fois, il y a beaucoup de détails à détailler, mais l'idée de base est que l'ajout d'un ou deux éléments à un tableau ne «pousse pas beaucoup la médiane».)

Answer 2

même idée à 5 tableaux.

D'abord, convertissez la question en une question plus générale. Trouver élément KTH N trié tableaux

1. Recherche (K/N) ième élément dans chaque tableau trié avec recherche binaire, par exemple K1, K2 ... KN

2. Kmin = min (K1 .. KN), Kmax = max (K1 ... KN)

3. Éliminer tous les éléments inférieurs à Kmin ou supérieurs à Kmax, par exemple, les éléments X ont été éliminés.

4. Maintenant, répétez le processus par trouver (K ​​- X) ième élément dans les tableaux triés avec des éléments restants

Answer 3

Vous n'avez pas besoin de faire une fusion complète des 5 tableaux.Vous pouvez faire un tri de fusion jusqu'à ce que vous ayez (l + n + o + p + q)/2 éléments alors vous avez la valeur médiane.