使用 C 查找向量的中值

Question

我是一名编程学生，对于我正在从事的项目，我必须做的事情是计算 int 值向量的中值，并且必须通过函数传递它来完成。此外，向量最初是使用我已经在我的代码中写下的 C++ 随机生成器 mt19937 随机生成的。我将使用排序函数和向量成员函数来执行此操作，例如 .begin() ， .end() 和 .size() 。

我应该确保找到向量的中值，然后输出它

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

代码：

 #include<iostream>
#include<vector>
#include<cstdlib>
#include<ctime>
#include<random>
#include<vector>
#include<cstdlib>
#include<ctime>
#include<random>

using namespace std;

double find_median(vector<double>);
double find_median(vector<double> len)
{
    {
        int i;
        double temp;
        int n=len.size();
        int mid;
        double median;
        bool swap;

        do
        {
            swap = false;
            for (i = 0; i< len.size()-1; i++)
            {
                if (len[i] > len[i + 1])
                {
                    temp = len[i];
                    len[i] = len[i + 1];
                    len[i + 1] = temp;
                    swap = true;
                }
            }
        }
        while (swap);

        for (i=0; i<len.size(); i++)
        {
            if (len[i]>len[i+1])
            {
                temp=len[i];
                len[i]=len[i+1];
                len[i+1]=temp;
            }
            mid=len.size()/2;
            if (mid%2==0)
            {
                median= len[i]+len[i+1];
            }
            else
            {
                median= (len[i]+0.5);
            }
        }
        return median;
    }
}
    int main()
    {
        int n,i;

        cout<<"Input the vector size: "<<endl;
        cin>>n;
        vector <double> foo(n);
        mt19937 rand_generator;
        rand_generator.seed(time(0));

        uniform_real_distribution<double> rand_distribution(0,0.8);
        cout<<"original vector: "<<" ";
        for (i=0; i<n; i++)
        {
            double rand_num=rand_distribution(rand_generator);
            foo[i]=rand_num;
            cout<<foo[i]<<" ";

        }
double median;
        median=find_median(foo);

        cout<<endl;

        cout<<"The median of the vector is:  "<<" ";
cout<<median<<endl;
    }

原文由 Nicole Alison 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

中位数由下式给出

const auto median_it = len.begin() + len.size() / 2;
std::nth_element(len.begin(), median_it , len.end());
auto median = *median_it;

对于偶数（向量的大小），您需要更精确一些。例如，您可以使用

assert(!len.empty());
if (len.size() % 2 == 0) {
    const auto median_it1 = len.begin() + len.size() / 2 - 1;
    const auto median_it2 = len.begin() + len.size() / 2;

    std::nth_element(len.begin(), median_it1 , len.end());
    const auto e1 = *median_it1;

    std::nth_element(len.begin(), median_it2 , len.end());
    const auto e2 = *median_it2;

    return (e1 + e2) / 2;

} else {
    const auto median_it = len.begin() + len.size() / 2;
    std::nth_element(len.begin(), median_it , len.end());
    return *median_it;
}

当然，我们可以通过多种不同的方式获取元素 e1 。我们也可以使用 max 或任何我们想要的。但是这一行很重要，因为 nth_element 只正确放置了第 n 元素，其余元素在此元素之前或之后排序，具体取决于它们是更大还是更小。这个范围是 未排序 的。

此代码保证 _平均具有线性复杂度_，即 O(N) ，因此它比排序渐近更好，即 O(N log N) 。

---

关于您的代码：

     for (i=0; i<len.size(); i++){
        if (len[i]>len[i+1])

这将不起作用，因为您在不存在的最后一次迭代中访问 len[len.size()] 。

原文由 overseas 发布，翻译遵循 CC BY-SA 4.0 许可协议