Modification algorithme de sélection pour sélectionner des éléments pondérés

Question

Je tente de modifier l'algorithme de sélection pour travailler avec la situation suivante:

Mon imput est une liste de nombres x1, x2, ..., XN (pas nécessairement commandé) .

Chacun de ces nombres a un poids "w". J'appelle W la somme de tous les poids. Si je fournis une valeur X, qui est supérieure à 0 mais non supérieure à W, comment puis-je trouver xi, de sorte que la somme des poids de tous les x dont l'indice est supérieur à i est inférieure à X, et Le poids de xi + la somme des poids de tous les éléments dont l'index est supérieur à i est supérieur ou égal à X.

Ceci est facilement accompli si nous trions tous les x en fonction de leur index, mais je souhaite le faire sans trier .

Answer 1

Vous ne devriez pas avoir à les trier si on vous donne l'identifiant i. On dirait que vous les voulez dans l'ordre de leurs identifiants, qui sont connus, donc il suffit de faire un passage dans la liste O (n) pour les mettre en ordre. Ensuite, suivez l'une des solutions affichées pour déterminer la valeur correcte de i. Suis-je mal compris le problème?

Mise à jour

permet donc dire que vous avez quatre valeurs, les identifiants sont comme ceci:

[ x4, x1, x3, x2 ] 

et leurs poids sont respectivement:

[ 14, 10, 5, 19 ] 

Tout ce que vous avez à faire est d'abord obtenir les listes dans l'ordre. Ce n'est pas la même chose que le tri parce que dans cette cause vous avez x1 .. xn, où les nombres sont tous contigus sans répétitions etc. Donc vous savez que le résultat sera une nouvelle liste de taille 4.

Faire un passer à travers la première liste. Dans ce cas, le premier numéro a un identificateur de 4, alors mettez-le dans la nouvelle liste à la position 4, et mettez le premier poids dans une nouvelle liste de poids également à la position 4. Ensuite sera mis en position 1, et ainsi de suite Quatrième.

Après celui-ci passe, vos listes ressembleront:

[ x1, x2, x3, x4 ] and [ 10, 19, 5, 14] 

Alors vous avez maintenant l'ordre que vous voulez. Il devient facile à ce stade de commencer juste à la fin de la liste de poids et de trouver la propriété que vous recherchez avec au plus une traversée de la liste.

Ainsi, il devrait être O (n).