使用C++查找向量的中值

Question

我是一名编程学生,对于我正在研究的项目,我必须做的事情是计算int值向量的中值,并且必须通过传递函数来完成.也将载体随机地使用C++,其我在code.I'm已经写下随机发生器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;
    }

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)因此它比sort更渐进地渐近复杂化O(N log N).

关于你的代码:

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

当您len[len.size()]在最后一次不存在的迭代中访问时,这将不起作用.

Answer 2

std::sort(len.begin(), len.end());
double median = len[len.size() / 2];

会做的。如果是偶数，您可能需要取中间两个元素的平均值size()，具体取决于您的要求：

0.5 * (len[len.size() / 2 - 1] + len[len.size() / 2]);