计算向量中存储的值的中位数 - 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

接受的答案使用 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，因为当向量大小为偶数时，中位数可能是分数。

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

Answer 5

我在下面给出了一个示例程序，该程序与 Max S. 的响应中的程序有些相似。为了帮助OP提高他的知识和理解，我做了一些改变。我已经：

a）将通过常量引用的调用更改为按值调用，因为排序将要更改向量中元素的顺序，（编辑：我刚刚看到罗布·肯尼迪在我准备我的文章时也说过这一点post)

b) 用更合适的向量 >::size_type 替换 size_t （实际上，后者的一个方便的同义词），

c) 将 size/2 保存到中间变量，

d)如果向量为空，则抛出异常，并且

e) 我还引入了条件运算符 (? :)。

实际上，所有这些更正都直接出自 Koenig 和 Moo 所著的《Accelerated C++》第 4 章。

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 6

我不太确定您对向量成员函数的用户的限制是什么，但是使用 [] 或 at() 进行索引访问将使访问元素更简单

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

：也可以像您当前正在做的那样使用像 begin() + offset 这样的迭代器，但是您需要首先使用 size()/2 计算正确的偏移量并添加到 begin()，而不是相反。此外，您还需要取消引用结果迭代器以访问此时的实际值：

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