Sélection efficace de la médiane et des éléments à gauche et à droite

Supposons que nous ayons un ensemble de codeurs. $S = \{ a_1,a_2,a_3,\ldots , a_N \}$ $N$

Chaque codeur a la cote et le nombre de médailles d'or qu'il avait remportées jusqu'à présent. $R_i$ $E_i$

Une société de logiciels souhaite embaucher exactement trois codeurs pour développer une application.

Pour embaucher trois codeurs, ils ont développé la stratégie suivante:

Ils classent d'abord les codeurs par ordre croissant de notes et par ordre décroissant de médailles d'or.
Dans cette liste organisée, ils sélectionnent les trois codeurs intermédiaires. Par exemple, si la liste organisée est ils sélectionnent codeurs. $(a_5,a_2,a_3,a_1,a_4)$ $(a_2,a_3,a_1)$

Nous devons maintenant aider l'entreprise en écrivant un programme pour cette tâche.

Contribution:

La première ligne contient , c'est-à-dire le nombre de codeurs. $N$

Ensuite, la deuxième ligne contient les notes du ème codeur. $R_i$ $i$

La troisième ligne contient le nombre de médailles d'or mises en sac par le ème codeur. $i$

Production:

N'affichez qu'une seule ligne contenant la somme des médailles d'or gagnées par les trois codeurs que l'entreprise sélectionnera.

algorithms algorithm-design Jack
la source

Les codeurs les mieux notés gagnent donc toujours moins de médailles ?? Sinon, quel ordre utilisez-vous réellement pour trier?

JeffE

Réponses:

Il s'agit d'un problème de sélection du ème plus petit élément de la liste résolue par une classe d'algorithmes appelés les algorithmes de sélection . Il existe des algorithmes déterministes de sélection du temps linéaire afin que votre problème puisse être résolu en temps linéaire en sélectionnant le $k$ ème plus petits éléments de la liste non triée d'origine. $n/2,n/2-1,n/2+1$

Opter
la source

Si vous le souhaitez, vous pouvez exécuter l'algorithme de sélection une fois pour trouver la médiane, puis trouver le minimum et le maximum dans les partitions droite et gauche respectivement d'un seul coup.

Zach Langley

@Sid @ Zach Langley Bonjour, pouvez-vous s'il vous plaît fournir le pseudo-code .i Je suis passé par le wiki paedia mais je me sens un peu difficile à comprendre. Vous pouvez donc s'il vous plaît fournir le pseudo-code Merci beaucoup!

Jack

@Jack, savez-vous comment fonctionne le tri rapide? L'algorithme de sélection aléatoire est essentiellement le même, sauf qu'il ne revient que d'un côté de chaque pivot.

Zach Langley

@Jack: L'article de wikipedia sur les algorithmes de sélection (lié dans la réponse de Sid) contient un pseudocode. Google fonctionne également.

JeffE

@Sid :: J'ai lu l'algorithme wiki (algorithme de sélection général basé sur la partition). Doit-on appeler la fonction select trois fois avec k = n / 2, k = n / 2-1, k / 2. la valeur de gauche, de droite lors de l'appel de la fonction select.Aussi dans la fonction de partition, quelle sera la valeur de la partition Index.

Jack