Calculer la Médiane des Valeurs Stockées Dans le Vecteur C++?
Je suis un étudiant en programmation, et pour un projet que je suis en train de travailler sur le, sur des choses que j'ai à faire est de calculer la valeur médiane d'un vecteur de valeurs int. Je suis pour ce faire, en utilisant uniquement la fonction de tri de la STL et le vecteur des fonctions de membre comme .begin()
, .end()
, et .size()
.
Je suis aussi censé assurez-je trouver la médiane si le vecteur a un nombre impair de valeurs ou d'un même nombre de valeurs.
Et je suis Coincé, ci-dessous, j'ai inclus ma tentative. Alors, où vais-je tort? Je vous serais reconnaissant si vous accepteriez de me donner quelques conseils ou des ressources pour aller dans la bonne direction.
Code:
int CalcMHWScore(const vector<int>& hWScores)
{
const int DIVISOR = 2;
double median;
sort(hWScores.begin(), hWScores.end());
if ((hWScores.size() % DIVISOR) == 0)
{
median = ((hWScores.begin() + hWScores.size()) + (hWScores.begin() + (hWScores.size() + 1))) / DIVISOR);
}
else
{
median = ((hWScores.begin() + hWScores.size()) / DIVISOR)
}
return median;
}
Merci!!
- Je ne suis pas sûr que l'utilisation d'une constante nommée pour la "2" est bien approprié.
- Merci pour l'attraper, j'ai marqué.
- Pour max heureux, je reformmatted votre code. J'ai aussi corrigé quelques parenthèse questions.
- Vous aurez probablement obtenir un nombre de lignes long de message d'erreur, finalement, se référant à la "sorte" de ligne. C'est parce que le paramètre d'entrée de votre fonction est
const
etsort
est d'essayer de modifier son contenu. Changement en passanthWScores
par valeur et non par référence const. - dites à votre professeur sur partial_sort comme il peut être utilisé pour trouver la médiane en O(n) fois. pas besoin d'aucune de ces fantaisie bizarre/même longueur contrôles des personnes ont été suggérant.
- Darid, à l'aide de partial_sort va toujours s'exécuter en O(n log n) de temps, vous aurez toujours besoin de comprendre que l'itérateur à utiliser pour le milieu, et vous aurez toujours besoin à la moyenne de deux valeurs intermédiaires si la longueur est la même.
Vous devez vous connecter pour publier un commentaire.
Vous faites un extra division et l'ensemble rend un peu plus complexe que cela doit l'être. Aussi, il n'y a pas besoin de créer un DIVISEUR quand 2 est en fait plus significatif dans le contexte.
Il n'est pas nécessaire de complètement trier le vecteur:
std::nth_element
pouvez le faire assez de travail pour mettre de la médiane dans la position correcte. Voir ma réponse à cette question pour un exemple.Bien sûr, cela ne fonctionne pas si votre professeur interdit l'utilisation du bon outil pour le travail.
nth_element
approche devrait être utilisée à la place de tri depuis l'ancien ne prend O(n) le temps tandis que le second prend O(n log n).nth_element
deux fois, à mettre à la fois le "central" éléments en place.nth_element
pourrait changer la position de la valeur déterminée par le premier appel. Le tableau n'aurait jamais deux éléments au bon endroit et au même moment; vous aurez besoin pour enregistrer la première valeur avant de faire l'appel de la deuxième.Ce qui suit est une simple fonction qui retourne la médiane d'un ensemble de valeurs en utilisant l'entrée des itérateurs. Il ne sera pas modifier le jeu de données d'origine, aux frais de l'allocation de mémoire.
Si vous voulez éviter le coût de l'allocation d'une copie de la base de données et sont prêts à modifier le dataset sous-jacent, vous pouvez l'utiliser à la place:
Ne pas le faire. Il est tout simplement votre code plus complexe. Vous avez probablement lu les lignes directrices de ne pas se servir des numéros de magie, mais la régularité vs étrangeté des nombres est une propriété fondamentale, de sorte que l'abstraction de cette offre aucun avantage, mais entrave la lisibilité.
Vous prenez un itérateur à la fin du vecteur, en prenant un autre itérateur qui pointe un passé la fin du vecteur, en ajoutant les itérateurs ensemble (ce qui n'est pas une opération qui a du sens), puis diviser la itérateur (qui ne fait pas de sens). C'est le cas plus compliqué; je vais vous expliquer quoi faire pour les impairs de la taille du vecteur d'abord et laisser la même taille de cas comme un exercice pour vous.
Encore une fois, vous êtes en divisant un itérateur. Ce que vous voulez faire est d'incrémenter un itérateur sur le début du vecteur par
hWScores.size() /2
éléments:Et la note que vous avez à de déréférencement des itérateurs pour obtenir les valeurs d'eux. Ce serait plus simple si vous avez utilisé les indices:
Je donne ci-dessous un exemple de programme qui est quelque peu similaire à celle de Max S. réponse. Pour aider les OP à l'avance de ses connaissances et de compréhension, j'ai fait un certain nombre de changements. J'ai:
a) a modifié l'appel par const référence à l'appel par valeur, depuis le tri va vouloir changer l'ordre des éléments dans votre vecteur, (EDIT: je viens de voir que robert Kennedy a aussi dit ceci alors que je préparais mon post)
b) remplacé size_t avec la plus appropriée vecteur
<int
>::size_type (en fait, une pratique synonyme de ce dernier),c) enregistrées taille/2 pour une variable intermédiaire,
d) levée d'une exception si le vecteur est vide, et
e) j'ai également introduit l'opérateur conditionnel (? :).
En fait, toutes ces corrections sont tout droit sorti du Chapitre 4 de "Accelerated C++" par Koenig et Moo.
Je ne suis pas exactement sûr de ce que votre restrictions à l'utilisateur des fonctions de membre du vecteur sont, mais l'indice d'accès avec
[]
ouat()
ferait accéder à des éléments plus simples:Vous pouvez également travailler avec les itérateurs comme
begin() + offset
comme vous êtes en train de faire, mais alors vous devez tout d'abord calculer le décalage correct avecsize()/2
et l'ajouter àbegin()
, pas l'inverse. Vous devez aussi avoir à déréférencer le résultant itérateur pour accéder à la valeur réelle à ce point:Accepté la réponse utilise
std::sort
qui n'a plus de travail que nous avons besoin. Les réponses que l'utilisationstd::nth_element
ne gèrent pas de la même taille de cas correctement.Nous pouvons faire un peu mieux que simplement en utilisant
std::sort
. Nous n'avons pas besoin de trier le vecteur complètement afin de trouver la médiane. Nous pouvons utiliserstd::nth_element
de trouver le moyen de l'élément. Depuis la médiane d'un vecteur par un nombre pair d'éléments est le moyen de les deux du milieu, nous avons besoin de faire un peu plus de travail pour trouver le moyen de l'élément dans ce cas.std::nth_element
assure que tous les éléments précédents, le milieu sont moins que celles du milieu. Elle ne garantit pas leur ordre au-delà que nous avons donc besoin d'utiliserstd::max_element
de trouver le plus grand élément précédant le milieu de l'élément.Vous pourriez envisager de retourner un
double
parce que la médiane peut être une fraction lorsque le vecteur a une même taille.