计算存储在Vector - C++中的值的中值？

Question

我是一名编程学生,对于我正在研究的项目,我必须做的事情是计算int值向量的中值.我这样做只使用排序功能从STL和矢量成员函数,如.begin(),.end()和.size().

我也应该确保我找到矢量具有奇数个值或偶数个值的中位数.

我被困了,下面我已经把我的尝试包括在内了.那我哪里错了？如果您愿意给我一些指导或资源以便朝着正确的方向前进,我将不胜感激.

码:

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

谢谢!!

Answer 1

没有必要对矢量进行完全排序:std::nth_element可以做足够的工作来将中位数放在正确的位置.有关示例,请参阅我对此问题的回答.

当然,如果您的老师禁止使用正确的工具来完成工作,那将无济于事.

Answer 2

你正在做一个额外的划分,整体上使它比它需要的更复杂.此外,当2在上下文中实际上更有意义时,不需要创建DIVISOR.

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

以下是一个简单的函数,它将使用输入迭代器返回一组值的中值.它不会以分配内存为代价修改原始数据集.

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

Answer 4

接受的答案使用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;
  }
}

您可能需要考虑返回 a，double因为当向量具有偶数大小时，中位数可能是分数。