Вычислить медиану значений, хранящихся в векторе - С++?

Ответ 1

Вы делаете дополнительное деление и в целом делаете это немного сложнее, чем нужно. Кроме того, нет необходимости создавать DIVISOR, когда 2 на самом деле более значимо в контексте.

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

Ответ 2

Нет необходимости полностью сортировать вектор: std::nth_element может сделать достаточно работы, чтобы поместить медиану в правильное положение. См. Мой ответ на этот вопрос для примера.

Конечно, это не поможет, если ваш учитель запрещает использовать правильный инструмент для задания.

Ответ 3

Следующая простая функция, которая вернет медиану набора значений с помощью итераторов ввода. Он не будет изменять исходный набор данных за счет выделения памяти.

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

Если вы хотите избежать затрат на выделение копии набора данных и готовы изменить базовый набор данных, вы можете использовать это вместо:

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

Ответ 4

const int DIVISOR = 2;

Не делай этого. Это просто делает ваш код более запутанным. Вероятно, вы читали инструкции о том, чтобы не использовать магические числа, но четкость и нечетность чисел является фундаментальным свойством, поэтому абстрагирование этого результата не приносит никакой пользы, но затрудняет читаемость.

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

Вы переносите итератор в конец вектора, беря еще один итератор, который указывает один за концом вектора, добавляя вместе итераторы (что не является операцией, которая имеет смысл), а затем деля итог итератор (что также не имеет смысла). Это более сложный случай; Сначала я объясню, что делать для вектора с нечетным размером, и оставьте случай с четным размером в качестве упражнения для вас.

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

Опять же, вы делите итератор. Вместо этого вы хотите увеличить итератор до начала вектора с помощью элементов hWScores.size() / 2:

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

И обратите внимание, что вам нужно разыгрывать итераторы, чтобы получить значения из них. Было бы проще, если бы вы использовали индексы:

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

Ответ 5

Ниже приводится примерная программа, которая несколько похожа на пример в ответе Макс. Чтобы помочь OP продвинуть свои знания и понимание, я внес ряд изменений. У меня есть:

a) изменил вызов с помощью ссылки const на вызов по значению, так как сортировка захочет изменить порядок элементов в вашем векторе, (EDIT: я просто видел, что Роб Кеннеди также сказал об этом, пока я готовил запись)

b) заменил size_t более подходящим вектором <int > :: size_type (фактически, удобным синонимом последнего),

c) сохраненный размер /2 для промежуточной переменной,

d) выбрасывает исключение, если вектор пуст, а

e) Я также ввел условный оператор (?:).

Собственно, все эти исправления прямо из главы 4 "Ускоренного С++" Koenig и 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];
}

Ответ 6

Я не совсем уверен, что ваши ограничения на пользовательские функции-члены вектора, но доступ к индексу с помощью [] или at() упростит доступ к элементам:

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

Вы также можете работать с итераторами, такими как begin() + offset, как вы сейчас делаете, но тогда вам нужно сначала вычислить правильное смещение с помощью size()/2 и добавить это к begin(), а не наоборот. Также вам необходимо разыменовать полученный итератор для доступа к фактическому значению в этой точке:

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

Ответ 7

Принятый ответ использует std::sort который выполняет больше работы, чем нам нужно. Ответы, использующие std::nth_element, не обрабатывают регистр четного размера правильно.

Мы можем сделать немного лучше, чем просто использовать std::sort. Нам не нужно сортировать вектор полностью, чтобы найти медиану. Мы можем использовать std::nth_element чтобы найти средний элемент. Поскольку медиана вектора с четным числом элементов является средним из двух средних, нам нужно проделать еще немного работы, чтобы найти другой средний элемент в этом случае. std::nth_element гарантирует, что все элементы, предшествующие середине, меньше, чем середина. Это не гарантирует их порядок, поэтому нам нужно использовать std::max_element чтобы найти самый большой элемент, предшествующий среднему элементу.

int CalcMHWScore(std::vector<int> hWScores) {
  assert(!hWScores.empty());
  const auto middleItr = hWScores.begin() + hWScores.size() / 2;
  std::nth_element(hWScores.begin(), middleItr, hWScores.end());
  if (hWScores.size() % 2 == 0) {
    const auto leftMiddleItr = std::max_element(hWScores.begin(), middleItr);
    return (*leftMiddleItr + *middleItr) / 2;
  } else {
    return *middleItr;
  }
}

Возможно, вы захотите вернуть значение double поскольку медиана может быть дробной, если вектор имеет четный размер.