我编写了一个程序,用户可以在向量中输入任意数量的值,它应该返回四分位数,但我不断得到“向量下标超出范围”错误：
#include "stdafx.h"
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <ios>
#include <vector>
int main () {
using namespace std;
cout << "Enter a list of numbers: ";
vector<double> quantile;
double x;
//invariant: homework contains all the homework grades so far
while (cin >> x)
quantile.push_back(x);
//check that the student entered some homework grades
//typedef vector<double>::size_type vec_sz;
int size = quantile.size();
if (size == 0) {
cout << endl << "You must enter your numbers . "
"Please try again." << endl;
return 1;
}
sort(quantile.begin(),quantile.end());
int mid = size/2;
double median;
median = size % 2 == 0 ? (quantile[mid] + quantile[mid-1])/2 : quantile[mid];
vector<double> first;
vector<double> third;
for (int i = 0; i!=mid; ++i)
{
first[i] = quantile[i];
}
for (int i = mid; i!= size; ++i)
{
third[i] = quantile[i];
}
double fst;
double trd;
int side_length = 0;
if (size % 2 == 0)
{
side_length = size/2;
}
else {
side_length = (size-1)/2;
}
fst = (size/2) % 2 == 0 ? (first[side_length/2]/2 + first[(side_length-1)/2])/2 : first[side_length/2];
trd = (size/2) % 2 == 0 ? (third[side_length/2]/2 + third[(side_length-1)/2])/2 : third[side_length/2];
streamsize prec = cout.precision();
cout << "The quartiles are" << setprecision(3) << "1st"
<< fst << "2nd" << median << "3rd" << trd << setprecision(prec) << endl;
return 0;
}
解决方法
而不是做std :: sort(quantile.begin(),quantile.end())而不是更便宜的方式
auto const Q1 = quantile.size() / 4; auto const Q2 = quantile.size() / 2; auto const Q3 = Q1 + Q2; std::nth_element(quantile.begin(),quantile.begin() + Q1,quantile.end()); std::nth_element(quantile.begin() + Q1 + 1,quantile.begin() + Q2,quantile.end()); std::nth_element(quantile.begin() + Q2 + 1,quantile.begin() + Q3,quantile.end());
这不会对整个数组进行排序,而只会对4个四分位数进行“组间”排序.这节省了完整的std :: sort所做的“内部组”排序.
如果您的分位数数组不大,那么这是一个小优化.但是std :: nth_element的缩放行为是O(N),而不是std :: sort的O(N log N).
