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

Question

我是一名编程学生，为了一个项目，我需要计算一个int向量的中位数值。我只能使用STL的sort函数以及vector成员函数，例如.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;
}

- Alex

---

不确定在这里使用一个命名常量来代表“2”是否恰当。 - Anon.

@Max - 谢谢你发现了它，我已经给它打了标签。 - Alex

为了让你更加愉快，我重新格式化了你的代码。我还修复了一些括号问题。 - Paul Nathan

最终您可能会得到一个很长的错误信息，它指向了“sort”行。这是因为您函数的输入参数是const，而sort正在尝试修改其内容。通过按值而非按常量引用传递hWScores来更改它。 - Rob Kennedy

告诉你的老师关于partial_sort，因为它可以在O(n)时间内找到中位数。不需要任何这些花哨的奇偶长度检查，人们一直在建议。 - Matthieu N.

Darid，使用partial_sort仍将以O(n log n)时间运行，您仍需要找出用于中间部分的迭代器，并且如果长度为偶数，则仍需要平均两个中间值。 - Rob Kennedy

Answer 1

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

当然，如果你的老师禁止使用正确的工具，则无济于事。

- Mike Seymour

---

实际上，应该使用nth_element方法而不是排序，因为前者仅需要O(n)的时间，而后者需要O(n log n)的时间。 - kennytm

正如我们所讨论的，你的解决方案只适用于“size”不是偶数的情况。 - Anonymous

@匿名，nth_element 对于偶数大小仍然有效。您只需要调用 nth_element 两次，将两个“中心”元素放置到正确的位置即可。 - Aaron McDaid

@AaronMcDaid，这真的有效吗？第二次调用nth_element可能会改变第一次调用确定的值的位置。数组永远不会同时拥有两个元素在正确的位置上；您需要在进行第二次调用之前保存第一个值。 - Mark Ransom

@MarkRansom，正如你所说，第一次调用的值可以被存储。在第二次调用nth_element函数后，您可以存储第二个值并计算中位数。您不需要这些值在向量中处于正确的位置。 - Marek Wawrzos

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

- Max Shawabkeh

---

等一下，我这里不应该传递常量引用吧？因为那样函数就不能对传递的向量进行排序了。 - Alex

正确的，就像Rob和Alexandros指出的那样 - 我在复制代码时没有注意到。在最后一次编辑中已经修复。 - Max Shawabkeh

如果您需要通过常量引用传递，那么可以创建向量的本地副本并对其进行排序。 - Maurice Reeves

排序的复杂度为n log(n)，而寻找中位数可以在log(n)时间内编码，不要使用排序来寻找大向量的中位数。 - nicodjimenez

scores.size() == 0 -> 段错误，scores.size() == 1 - 段错误 - Sild

这个能用于双精度浮点数吗：std::vector<double> 分数？ - PlsWork

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 类型。

- Indiana Kernick

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

- jamesdlin

Answer 5

我提供以下示例程序，与Max S.的回答中的程序有些相似。为了帮助OP提高他的知识和理解，我做出了一些更改。我已经：

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

b) 用更合适的vector<int>::size_type（实际上是后者的方便同义词）替换了size_t，

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

d) 如果向量为空，则抛出异常，以及

e) 我还引入了条件运算符（？：）。

事实上，所有这些更正都直接来自Koenig和Moo的《加速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];
}

- Alexandros Gezerlis

Answer 6

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

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

你也可以像你目前正在做的那样使用迭代器，例如begin() + offset，但是你需要先用size()/2计算出正确的偏移量，然后将其加到begin()上，而不是相反。此外，你需要解引用结果迭代器以访问该点的实际值：

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

- sth