Médiane de 5 tableaux triés
J'essaie de trouver la solution pour la médiane de 5 tableaux triés. C'était une des questions d'entrevue.
La solution à laquelle je pouvais penser était de fusionner les 5 tableaux, 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 la médiane peut être un 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 tableaux . Que faire si les matrices sont de même taille , est-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 tous les pointeurs.
Quelques précisions/questions que j'ai posées à l'intervieweur:
Sont les tableaux de même longueur
=> Pas de
Je suppose qu'il y aurait un chevauchement dans les valeurs de tableaux
= > Oui
En tant qu'exercice, je pense que la logique pour 2 tableaux ne s'étend pas . Voici un essai:
Appliquer la logique ci dessus de 2 tableaux pour dire 3 tableaux:
[3,7,9] [4,8,15] [2,3,9] ... médianes 7,8,3
jeter éléments [3,7,9] [4,8] [3,9] .. médianes 7,6,6
jeter des éléments [3,7] [8] [9] ..les médianes 5,8,9 ...
jeter des éléments [7] [8] [9] .. médiane = 8 ... Ce ne semble pas être correcte ?
La fusion des éléments triés => [2,3,4,7,8,9,15] => médiane attendue = 7
3 réponses
(C'est une généralisation de votre idée pour deux tableaux.)
Si vous commencez par regarder les cinq médianes des cinq tableaux, évidemment la médiane globale doit être entre la plus petite et la plus grande des cinq médianes.
La preuve va quelque chose comme ceci: si a est le min des médianes, et b est le max des médianes, alors chaque tableau a moins de la moitié de ses éléments inférieurs à a et moins de la moitié de ses éléments supérieurs à B. Le résultat suit.
Donc dans le tableau contenant a, jeter les nombres inférieurs à a; dans le tableau contenant b, jeter les nombres supérieurs à B... Mais seulement jeter le même nombre d'éléments des deux tableaux.
C'est-à-dire que si A est j éléments du 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) du tableau de a et les derniers éléments min(j,k) du tableau de B.
Itérer jusqu'à ce que vous soyez à 1 ou 2 éléments au total.
Chacun de ces les opérations (c'est-à-dire, trouver la médiane d'un tableau trié et jeter k éléments du début ou de la fin d'un tableau) sont des temps constants. Donc, chaque itération est un temps constant.
Chaque itération jette (plus de) la moitié des éléments d'au moins un tableau, et vous ne pouvez faire ce journal(n) fois pour chacun des cinq tableaux... Donc, l'algorithme global est log (n).
[mise à Jour]
Comme le souligne Himadri Choudhury dans les commentaires, ma solution est incomplète; il y a beaucoup de les détails et le coin des cas, à s'inquiéter. 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).
Soit " a "le plus petit des médianes inférieures, et" b " le plus grand des médianes supérieures. S'il y a plusieurs tableaux avec la plus petite médiane inférieure et / ou plusieurs tableaux avec le plus grande médiane supérieure, choisissez a et b à partir de différents tableaux (c'est l'un de ces cas de coin).
Maintenant, en empruntant la suggestion de Himadri: effacer tous les éléments jusqu'à et y compris A de son tableau, et tous les éléments jusqu'à et y compris B de son tableau, en prenant soin de supprimer 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, car sinon nous aurions pu choisir l'un d'entre eux à partir 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.
Itérer tant que vous avez trois tableaux ou plus. Mais une fois que vous êtes à seulement un ou deux tableaux, vous devez changer votre stratégie pour être exclusif au lieu d'inclusif; vous effacez seulement jusqu'à mais pas y compris a et jusqu'à mais pas y compris B. continuez comme ça tant que les deux tableaux restants ont un ou deux tableaux au moins trois éléments (garantissant que vous faites des progrès).
Enfin, vous réduirez à quelques cas, dont le plus délicat est 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 le faire en temps constant. (Encore une fois, il y a un tas de détails à marteler, mais l'idée de base est que l'ajout d'un ou deux éléments à un tableau ne " pousse pas la médiane autour de" beaucoup.)
Devrait être assez droit pour appliquer la même idée à 5 tableaux.
Tout d'abord, convertissez la question en question plus générale. Trouver le Kème élément dans N tableaux triés
-
Trouvez (K / N) E élément dans chaque tableau trié avec la recherche binaire, disons K1, K2... KN
-
Kmin = min (K1 ... Kn), Kmax = max (K1 ... KN)
Jetez tous les éléments inférieurs à Kmin ou plus grands que Kmax, disons que X éléments ont été jetés.
-
Maintenant, répétez le processus en trouver (K - x)e élément dans les tableaux triés avec les éléments restants
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.