Проблемы со средним значением функции C ++

Question

Я пытаюсь создать проблему в zybooks (C ++), которая находит медианное значение вектора.Вот функция, которую я написал для этого:

double FindMedianScore(vector<int>& scores)
{
   sort(scores.begin(), scores.end());
   int median_score;
   if ((scores.size() % 2) == 0)
   {
      median_score = (scores.at((scores.size() / 2) - 1) + 
scores.at(scores.size() / 2)) / 2;   
   }
   else if ((scores.size() % 2) != 0)
   {
      median_score = scores.at(scores.size() / 2);
   }
   return median_score;    
}

Во всех тестах, которые он проходит, за исключением теста случайных значений.zybooks дает функции вектор 250 случайных значений и хочет получить медиану.Насколько я могу судить, в моем коде нет ничего плохого, но я провалю тест, что бы я ни менял.Есть мысли?

Answer 1

Есть несколько проблем с этим кодом.Некоторые из них уже были указаны в комментариях.

Самая большая из них была идентифицирована с donpsabance: ваша переменная median_score объявлена ​​как int, даже если вы возвращаете double.Вычисление, которое усредняет две медианы:

median_score = (scores.at((scores.size() / 2) - 1) + scores.at(scores.size() / 2)) / 2; 

, выполняется с использованием целочисленной арифметики, поэтому, если в делении есть остаток, он не будет отражен в значении, которое выreturn.

SM обнаружил еще одну возможную проблему в зависимости от того, как построены проверочные тесты: ваш код предполагает, что входной вектор имеет ненулевую длину.Если это гарантировано, то у вас все хорошо.Если нет, то ваш код выдаст исключение.

Это должно решить проблемы правильности , но ваш код все еще можно улучшить несколькими другими способами.

Первое, что мне не нравится, это предложение else if:

else if ((scores.size() % 2) != 0)

Вам не нужно условное if, поскольку это единственное условие, которое можетбыть правдой, как только исполнение достигнет else.Просто используйте else.

Во-вторых, если вы добавите явную проверку для входного вектора нулевой длины, вы можете индексировать непосредственно в этот вектор вместо необходимости вызывать at.Помимо производительности, явная проверка в любом случае является хорошей идеей, поскольку она позволяет генерировать более подходящее исключение.

Слегка переписанный, ваш код может выглядеть примерно так:

double FindMedianScore(vector<int>& scores)
{
    // Ensure input vector contains at least one element.
    const auto length = scores.size();
    if (length == 0)
    {
        throw std::domain_error("'scores' vector is empty.");
    }

    // Sort the elements of the vector in place.
    std::sort(std::begin(scores), std::end(scores));

    // Determine the median.
    double median_score;
    if ((length % 2) == 0)
    {
       median_score = static_cast<double>(scores[(length / 2) - 1] + scores[length / 2]) / 2.0;
    }
    else
    {
        median_score = scores[length / 2];
    }
    return median_score;  
}

Илидаже:

double FindMedianScore(vector<int>& scores)
{
    // Ensure input vector contains at least one element.
    const auto length = scores.size();
    if (length == 0)
    {
        throw std::domain_error("'scores' vector is empty.");
    }

    // Sort the elements of the vector in place.
    std::sort(std::begin(scores), std::end(scores));

    // Determine the median.
    double median_score = scores[length / 2];
    if ((length % 2) == 0)
    {
       median_score += scores[(length / 2) - 1];
       median_score /= 2.0;
    }
    return median_score;  
}

Но, если подумать немного сложнее, вы увидите, что есть еще лучший способ.Здесь мы сортируем весь вектор, что является операцией O (n log n).Но на самом деле вам не нужно сортировать весь вектор, чтобы определить медиану.Как оказалось, стандартная библиотека C ++ имеет идеальный алгоритм для того, что вам нужно: std::nth_element.Это делает только частичную сортировку и имеет время выполнения O (n).

double FindMedianScore(vector<int>& scores)
{
    using std::begin;
    using std::next;
    using std::end;

    // Ensure input vector contains at least one element.
    const auto length = scores.size();
    if (length == 0)
    {
        throw std::domain_error("'scores' vector is empty.");
    }

    const auto halfLength = (length / 2);

    // Do an in-place partial sort on the vector, rearranging elements such that
    // the middle element is as if the vector were fully sorted.
    std::nth_element(begin(scores), next(begin(scores), halfLength), end(scores);

    // Determine the median.
    // If the container's length is odd, the median element is the one exactly in
    // the middle. Otherwise, if the container's length is even, the median is the
    // mean of the two median values. Since std::nth_element guarantees that all
    // preceding elements are less-than or equal to the target, and all subsequent
    // elements are greater-than or equal to the target, we can retrieve the
    // other median value by just calling std::max_element. This is more efficient
    // than doing another partial sort with std::nth_element.
    double median_score = scores[halfLength];
    if ((length % 2) == 0)
    {
       median_score += *std::max_element(begin(scores), next(begin(elements), halfLength));
       median_score /= 2.0;
    }
    return median_score;  
}