c++ - 对具有重复项的列表中的索引进行排序
问题描述
我正在尝试获取可能包含重复项的列表中字符串的排序位置。
我不关心重复项的未定义顺序,但我想要一个全局排序。
这是我迄今为止最好的尝试:
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
void display(const std::vector<int> &array)
{
for (const auto & value : array)
std::cout << value << " ";
std::cout << std::endl;
}
std::vector<int> sortIndexes(const std::vector<std::string> &values)
{
std::vector<int> indexes(values.size());
std::iota(indexes.begin(), indexes.end(), 0);
std::stable_sort(indexes.begin(), indexes.end(), [&values](const size_t first, const size_t second)
{
return values.at(first) <= values.at(second);
});
return indexes;
}
int main (void)
{
display(sortIndexes({"b", "a", "c"})); // Expecting: 1 0 2 Result: 1 0 2
display(sortIndexes({"c", "c", "a"})); // Expecting: 1 2 0 or 2 1 0 Result: 2 1 0
display(sortIndexes({"c", "a", "c"})); // Expecting: 1 0 2 or 2 0 1 Result: 1 2 0
return 0;
}
有没有另一种方法来获得预期的输出?
编辑:
我错过了解决我的问题的严格比较 + 'inverseIndexes' 部分。这是更新的代码:
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
void display(const std::vector<int> & array)
{
for (const auto & value : array)
std::cout << value << " ";
std::cout << std::endl;
}
std::vector<int> inverseIndexes(const std::vector<int> & indexes)
{
std::vector<int> inverse(indexes.size());
for (size_t i = 0; i < indexes.size(); ++i)
inverse[indexes[i]] = i;
return inverse;
}
std::vector<int> sortIndexes(const std::vector<std::string> & values)
{
std::vector<int> indexes(values.size());
std::iota(indexes.begin(), indexes.end(), 0);
std::stable_sort(indexes.begin(), indexes.end(), [&values](const size_t first, const size_t second)
{
return values.at(first) < values.at(second);
});
return indexes;
}
int main (void)
{
display(inverseIndexes(sortIndexes({"b", "a", "c"})));
display(inverseIndexes(sortIndexes({"c", "c", "a"})));
display(inverseIndexes(sortIndexes({"c", "a", "c"})));
return 0;
}
解决方案
的比较函数std::stable_sort
应该是严格的“小于”,而不是“小于或等于”。因此,您只需要修复此行:
return values.at(first) < values.at(second);