计算存储在向量中的值的中位数 - C++？

Compute Median of Values Stored In Vector - C++?

提问by Alex

I'm a programming student, and for a project I'm working on, on of the things I have to do is compute the median value of a vector of int values. I'm to do this using only the sort function from the STL and vector member functions such as .begin(), .end(), and .size().

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

I'm also supposed to make sure I find the median whether the vector has an odd number of values or an even number of values.

我还应该确保找到向量的中位数是奇数个值还是偶数个值。

And I'm Stuck, below I have included my attempt. So where am I going wrong? I would appreciate if you would be willing to give me some pointers or resources to get going in the right direction.

而我卡住，下面我已经列入我的尝试。那么我哪里出错了？如果您愿意给我一些指示或资源以朝着正确的方向前进，我将不胜感激。

Code:

代码：

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

Thanks!!

谢谢！！

采纳答案by Max Shawabkeh

You are doing an extra division and overall making it a bit more complex than it needs to be. Also, there's no need to create a DIVISOR when 2 is actually more meaningful in context.

你正在做一个额外的除法，总体上使它比它需要的要复杂一些。此外，当 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];
    }
  }
}

回答by Mike Seymour

There is no need to completely sort the vector: std::nth_elementcan do enough work to put the median in the correct position. See my answer to this questionfor an example.

不需要对向量进行完全排序：std::nth_element可以做足够的工作来将中位数放在正确的位置。以我对这个问题的回答为例。

Of course, that doesn't help if your teacher forbids using the right tool for the job.

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

回答by jamesdlin

const int DIVISOR = 2;

Don't do this. It just makes your code more convoluted. You've probably read guidelines about not using magic numbers, but evenness vs. oddness of numbers is a fundamental property, so abstracting this out provides no benefit but hampers readability.

不要这样做。它只会让你的代码更加复杂。您可能已经阅读了有关不使用幻数的指南，但数字的偶数与奇数是一个基本属性，因此将其抽象出来没有任何好处，但会降低可读性。

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

You're taking an iterator to the end of the vector, taking another iterator that points one past the end of the vector, adding the iterators together (which isn't an operation that makes sense), and then dividing the resulting iterator (which also doesn't make sense). This is the more complicated case; I'll explain what to do for the odd-sized vector first and leave the even-sized case as an exercise for you.

您将一个迭代器带到向量的末尾，使用另一个指向向量末尾的迭代器，将迭代器加在一起（这不是一个有意义的操作），然后将结果迭代器（它也没有道理）。这是更复杂的情况；我将首先解释如何处理奇数大小的向量，然后将偶数大小的向量留作练习。

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

Again, you're dividing an iterator. What you instead want to do is to increment an iterator to the beginning of the vector by hWScores.size() / 2elements:

同样，您正在划分迭代器。相反，您想要做的是通过hWScores.size() / 2元素将迭代器增加到向量的开头：

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

And note that you have to dereferenceiterators to get values out of them. It'd be more straightforward if you used indices:

请注意，您必须取消引用迭代器才能从中获取值。如果您使用索引会更简单：

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

回答by Alexandros Gezerlis

I give below a sample program that is somewhat similar to the one in Max S.'s response. To help the OP advance his knowledge and understanding, I have made a number of changes. I have:

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

a) changed the call by const reference to call by value, since sort is going to want to change the order of the elements in your vector, (EDIT: I just saw that Rob Kennedy also said this while I was preparing my post)

a) 将按常量引用的调用更改为按值调用，因为 sort 将要更改向量中元素的顺序，（编辑：我刚看到 Rob Kennedy 在我准备帖子时也说过这个）

b) replaced size_t with the more appropriate vector<int>::size_type (actually, a convenient synonym of the latter),

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

c) saved size/2 to an intermediate variable,

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

d) thrown an exception if the vector is empty, and

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

e) I have also introduced the conditional operator (? :).

e) 我还介绍了条件运算符 (? :)。

Actually, all of these corrections are straight out of Chapter 4 of "Accelerated C++" by Koenig and Moo.

实际上，所有这些更正都直接来自 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];
}

回答by Indiana Kernick

The accepted answer uses std::sortwhich does more work than we need it to. The answers that use std::nth_elementdon't handle the even size case correctly.

接受的答案使用std::sortwhich 做了比我们需要的更多的工作。使用的答案std::nth_element不能正确处理偶数大小的情况。

---

---

We can do a little better than just using std::sort. We don't need to sort the vector completely in order to find the median. We can use std::nth_elementto find the middle element. Since the median of a vector with an even number of elements is the average of the middle two, we need to do a little more work to find the other middle element in that case. std::nth_elementensures that all elements preceding the middle are less than the middle. It doesn't guarantee their order beyond that so we need to use std::max_elementto find the largest element preceding the middle 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;
  }
}

You might want to consider returning a doublebecause the median may be a fraction when the vector has an even size.

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

回答by sth

I'm not exactly sure what your restrictions on the user of member functions of vector are, but index access with []or at()would make accessing elements simpler:

我不确定您对 vector 成员函数的用户的限制是什么，但是使用[]orat()进行索引访问会使访问元素变得更简单：

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

You can also work with iterators like begin() + offsetlike you are currently doing, but then you need to first calculate the correct offset with size()/2and add that to begin(), not the other way around. Also you need to dereference the resulting iterator to access the actual value at that point:

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

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