我正在尝试构造一个函数,接受一个 vector ,对其进行排名,对其进行排序,并输出排序和排名后的 vector 以及值的原始定位。例如: 输入:[10,332,42,0.9,0] 输出:[3, 5, 4, 2, 1]
我使用了这个堆栈溢出question (特别是马吕斯的答案)作为引用指南,但是我现在被我的代码困住了,不明白问题出在哪里。 我正在运行 C++03。
我遇到的错误之一是
错误:在我的
。if
语句中,数组下标的“const float*[float]”类型无效
//Rank the values in a vector
std::vector<float> rankSort(const float *v_temp, size_t size)
{
vector <float> v_sort;
//create a new array with increasing values from 0 to n-1
for(unsigned i = 0; i < size; i++)
{
v_sort.push_back(i);
}
bool swapped = false;
do
{
for(unsigned i = 0; i < size; i++)
{
if(v_temp[v_sort[i]] > v_temp[v_sort[i+1]]) //error line
{
float temp = v_sort[i];
v_sort[i] = v_sort[i+1];
v_sort[i+1] = temp;
swapped = true;
}
}
}
while(swapped);
return v_sort;
}
std::vector<float> rankSort(const std::vector<float> &v_temp)
{
return rankSort(&v_temp[0], v_temp.size());
}
最佳答案
您的问题是对排名的误解。数组索引为 size_t
不是float
,因此您需要返回 vector<size_t>
不是vector<float>
.
也就是说,您的排序是O(n2)。如果您愿意使用更多内存,我们可以将时间缩短至 O(n log(n)):
vector<size_t> rankSort(const float* v_temp, const size_t size) {
vector<pair<float, size_t> > v_sort(size);
for (size_t i = 0U; i < size; ++i) {
v_sort[i] = make_pair(v_temp[i], i);
}
sort(v_sort.begin(), v_sort.end());
pair<double, size_t> rank;
vector<size_t> result(size);
for (size_t i = 0U; i < size; ++i) {
if (v_sort[i].first != rank.first) {
rank = make_pair(v_sort[i].first, i);
}
result[v_sort[i].second] = rank.second;
}
return result;
}
编辑:
是的,当使用 vector<float>
时,这实际上变得更简单了。而不是float[]
:
vector<size_t> rankSort(const vector<float>& v_temp) {
vector<pair<float, size_t> > v_sort(v_temp.size());
for (size_t i = 0U; i < v_sort.size(); ++i) {
v_sort[i] = make_pair(v_temp[i], i);
}
sort(v_sort.begin(), v_sort.end());
pair<double, size_t> rank;
vector<size_t> result(v_temp.size());
for (size_t i = 0U; i < v_sort.size(); ++i) {
if (v_sort[i].first != rank.first) {
rank = make_pair(v_sort[i].first, i);
}
result[v_sort[i].second] = rank.second;
}
return result;
}
关于c++ - 如何在 C++ 中对 vector 进行排序和排名(不使用 C++11),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41184561/