sacar - Calcule la mediana de los valores almacenados en Vector-C++?

ejemplos de vectores en programacion

Question

Soy un estudiante de programación, y para un proyecto en el que estoy trabajando, una de las cosas que tengo que hacer es calcular el valor medio de un vector de valores int. Voy a hacer esto usando solo la función de ordenamiento de las funciones de miembro de vector y STL como .begin() , .end() y .size() .

También se supone que debo asegurarme de encontrar la mediana si el vector tiene un número impar de valores o un número par de valores.

Y estoy atorado , a continuación he incluido mi intento. Entonces, ¿dónde me estoy equivocando? Le agradecería si estuviera dispuesto a darme algunos consejos o recursos para avanzar en la dirección correcta.

Código:

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;
}

¡¡Gracias!!

Answer 1

Doy a continuación un programa de muestra que es algo similar al de la respuesta de Max S. Para ayudar al OP a avanzar en su conocimiento y comprensión, he realizado una serie de cambios. Yo tengo:

a) cambié la llamada por referencia de const para llamar por valor, ya que la ordenación va a querer cambiar el orden de los elementos en su vector, (EDIT: Acabo de ver que Rob Kennedy también dijo esto mientras preparaba mi publicación)

b) reemplazó size_t con el vector más apropiado <int > :: size_type (en realidad, un conveniente sinónimo de este último),

c) tamaño guardado / 2 a una variable intermedia,

d) lanza una excepción si el vector está vacío, y

e) También he introducido el operador condicional (? :).

De hecho, todas estas correcciones vienen directamente del Capítulo 4 de "C ++ acelerado" de Koenig y Moo.

double median(vector<int> vec)
{
typedef vector<int>::size_type vec_sz;
vec_sz size = vec.size();
if (size == 0)
throw domain_error("median of an empty vector");
sort(vec.begin(), vec.end());
vec_sz mid = size/2;
return size % 2 == 0 ? (vec[mid] + vec[mid-1]) / 2 : vec[mid];
}

Answer 2

Estás haciendo una división extra y, en general, haciéndola un poco más compleja de lo necesario. Además, no es necesario crear un DIVISOR cuando 2 tiene más sentido en el contexto.

double CalcMHWScore(vector<int> scores)
{
size_t size = scores.size();
if (size == 0)
{
return 0; // Undefined, really.
}
else
{
sort(scores.begin(), scores.end());
if (size % 2 == 0)
{
return (scores[size / 2 - 1] + scores[size / 2]) / 2;
}
else
{
return scores[size / 2];
}
}
}

Answer 3

La siguiente es una función simple que devolverá la mediana de un conjunto de valores utilizando los iteradores de entrada. No modificará el conjunto de datos original, a costa de asignar memoria.

// Get the median of an unordered set of numbers of arbitrary
// type without modifying the underlying dataset.
template <typename It>
auto Median(It begin, It end)
{
using T = typename std::iterator_traits<It>::value_type;
std::vector<T> data(begin, end);
std::nth_element(data.begin(), data.begin() + data.size() / 2, data.end());
return data[data.size() / 2];
}

Si desea evitar el costo de asignar una copia del conjunto de datos y está dispuesto a modificar el conjunto de datos subyacente, puede usar esto en su lugar:

// Get the median of an unordered set of numbers of arbitrary
// type (this will modify the underlying dataset).
template <typename It>
auto Median(It begin, It end)
{
const auto size = std::distance(begin, end)
std::nth_element(begin, begin + size / 2, end);
return *std::next(begin, size / 2);
}

Answer 4

No es necesario ordenar completamente el vector: std::nth_element puede hacer suficiente trabajo para colocar la mediana en la posición correcta. Vea mi respuesta a esta pregunta para un ejemplo.

Por supuesto, eso no ayuda si su maestro prohíbe usar la herramienta correcta para el trabajo.

Answer 5

No estoy exactamente seguro de cuáles son sus restricciones sobre el usuario de las funciones miembro de vector, pero el acceso de índice con [] o at() facilitaría el acceso a los elementos:

median = hWScores.at(hWScores.size() / 2);

También puede trabajar con iteradores como begin() + offset como lo está haciendo actualmente, pero luego necesita calcular primero el desplazamiento correcto con size()/2 y agregarlo para begin() , y no al revés. También necesita desreferenciar el iterador resultante para acceder al valor real en ese punto:

median = *(hWScores.begin() + hWScores.size()/2)

Answer 6

const int DIVISOR = 2;

No hagas esto Simplemente hace que tu código sea más intrincado. Probablemente hayas leído las pautas sobre el uso de números mágicos, pero la uniformidad y la rareza de los números es una propiedad fundamental, por lo que resumir esto no proporciona ningún beneficio, pero dificulta la legibilidad.

if ((hWScores.size() % DIVISOR) == 0)
{
median = ((hWScores.begin() + hWScores.size()) + (hWScores.begin() + (hWScores.size() + 1))) / DIVISOR);

Está tomando un iterador al final del vector, tomando otro iterador que apunta uno más allá del final del vector, sumando los iteradores (lo cual no es una operación que tenga sentido), y luego dividiendo el iterador resultante (que tampoco tiene sentido). Este es el caso más complicado; Primero explicaré qué hacer para el vector de tamaño impar y dejaré el caso de tamaño par como ejercicio para ti.

}
else
{
median = ((hWScores.begin() + hWScores.size()) / DIVISOR)

De nuevo, estás dividiendo un iterador. Lo que desea hacer en su lugar es incrementar un iterador al principio del vector mediante hWScores.size() / 2 elementos:

 median = *(hWScores.begin() + hWScores.size() / 2);

Y tenga en cuenta que debe eliminar los iteradores para obtener valores de ellos. Sería más sencillo si usa índices:

 median = hWScores[hWScores.size() / 2];