在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

您正在做一个额外的划分，并且总体上使得它比需要更复杂一点。另外，当2在上下文中实际上更有意义时，不需要创建DIVISOR。

double CalcMHWScore(vector<int> scores) 
{ 
    size_t size = scores.size(); 

    if (size == 0) 
    { 
    return 0; // Undefined, really. 
    } 
    else if (size == 1) 
    { 
    return scores[0]; 
    } 
    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 2

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 3

我不完全相信你对向量的成员函数的用户限制是什么，但[]或at()索引访问将使访问元素简单：

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

您也可以像begin() + offset迭代器的工作就像你正在做，但你必须先计算正确的偏移与size()/2，并添加到begin()，而不是周围的其他方式。你也需要取消引用导致迭代器在该点访问的实际值：

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

Answer 4

我在下面，有点类似于一个在马克斯S.的响应的示例程序。为了帮助OP提高他的知识和理解，我做了一些改变。我有：

a）通过const引用改变了调用的值，因为排序是要改变你的向量中的元素的顺序，（编辑：我刚才看到，罗布肯尼迪也说这一点我正准备我替换为size_t与更合适的载体<int> :: size_type的（实际上，后者）的方便的同义词，

c）中保存的大小/ 2后）

b）至一个中间变量，

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 5

没有必要载体完全排序：std::nth_element可以做足够的工作，把中位数在正确的位置。以我的答案this question为例。

当然，如果你的老师禁止使用正确的工具进行工作，这并没有帮助。

Answer 6

以下是一个简单函数，它将使用输入迭代器返回一组值的中值。它不会修改原始数据集，代价是分配内存。与“功课”

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