问题是:我需要对字符串向量进行精确的排序。假设我们有一个常数向量或一个具有精确顺序的数组:
vector<string> correctOrder = {"Item3", "Item1", "Item5", "Item4", "Item2"};
接下来,我们有一个动态输入向量,它将有相同的项目,但它们可能是混合的,而且数量较少。
vector<string> incommingVector = {"Item1", "Item5", "Item3"};
因此,我需要按照顺序排序incomming
向量,就像第一个向量,correctOrder
,结果必须是:
vector<string> sortedVector = {"Item3", "Item1", "Item5"};
我认为正确的顺序可以用另一种方式表示,但无法理解。有人能帮帮我吗?
发布于 2018-11-23 02:45:01
您可以创建自己的函子,按照模板向量顺序对矢量进行排序,如下代码所解释:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
struct MyComparator
{
//static const int x = 9;
const std::vector<std::string> correctOrder{"Item1", "Item2", "Item3", "Item4", "Item5"};
bool operator() (const std::string& first,const std::string& second )
{
auto firstitr = std::find(correctOrder.begin(),correctOrder.end(),first);
auto seconditr = std::find(correctOrder.begin(),correctOrder.end(),second);
return firstitr < seconditr;
}
};
void printVector(const std::vector<std::string>& input)
{
for(const auto&elem:input)
{
std::cout<<elem<<" , ";
}
std::cout<<std::endl;
}
int main()
{
std::vector<string> incomingVector = {"Item3", "Item5", "Item1"};
std::cout<<"vector before sort... "<<std::endl;
printVector(incomingVector);
std::sort(incomingVector.begin(),incomingVector.end(),MyComparator());
std::cout<<"vector after sort...."<<std::endl;
printVector(incomingVector);
return 0;
}
发布于 2018-11-23 02:12:12
如果默认的比较还不够(词汇表比较),那么您可以做的最简单的事情就是为排序函数提供一个兰卜达,它告诉它哪个字符串放在第一位。您可以有一个unordered_map
,其中字符串在correctorder
向量中作为键,它们在排序数组中的对应位置作为值。
cmp
函数将简单地比较您在incommingVector
中提供的键的值。
unordered_map<string, int> my_map;
for(int i = 0 ; i < correctorder.size() ; i++)
my_map[correctorder[i]]=i;
auto cmp =[&my_map](const string& s, const string& s1){
return my_map[s] < my_map[s1];
}
sort(incommingVector.begin(), incommingVector.end() , cmp);
发布于 2018-11-23 02:21:07
您可以利用std::unordered_map
,即用于在恒定时间内将字符串映射为整数的哈希表。您可以使用它来找出给定字符串在向量correctOrder
中在O(1)
中所占的位置,这样就可以在恒定时间内比较向量incomming
中的两个字符串。
考虑以下函数sort_incomming_vector()
#include <unordered_map>
using Vector = std::vector<std::string>;
void sort_incomming_vector(const Vector& correctOrder /*N*/, Vector& incomming /*M*/)
{
std::unordered_map<std::string, int> order;
// populate the order hash table in O(N) time
for (size_t i = 0; i < correctOrder.size(); ++i)
order[correctOrder[i]] = i;
// sort "incomming" in O(M*log M) time
std::sort(incomming.begin(), incomming.end(),
[&order](const auto& a, const auto& b) { // sorting criterion
return order[a] < order[b];
}
);
}
哈希表order
将字符串映射为整数,由此产生的整数被传递给排序算法std::sort
的lambda (即排序准则)用于比较向量incomming
中的一对字符串,以便排序算法能够相应地对它们进行置换。
如果correctOder
包含N
元素,incomming
包含M
元素,那么哈希表可以用O(N)
时间初始化,incomming
可以按O(M*log M)
时间排序。因此,整个算法将在O(N + M*log M)
时间内运行。
如果N
比M
大得多,则该解是最优的,因为占优项是N
,即O(N + M*log M)
~ O(N)
。
https://stackoverflow.com/questions/53444532
复制相似问题