什么是根据它们在句子中的位置对这些字符串输入进行排序的更快的方法？

Question

为国家信息学奥林匹克运动会的实践偶然发现了一个问题:用户输入句子中的单词数量(n)以及输入单词的收益以及用空格分隔的位置.系统会要求您输入正确的单词顺序.

例如:

输入:

4
this 1
sentence 4
is 2
a 3

输出:

this is a sentence

限制:

1 <= N <= 3 * 10^5
1 <= Size of a word <= 50

我试图使用unordered_map解决这个问题,事实证明这很快解决了所有测试案例只需0.588秒,这使我的解决方案成为45中最快的第五个.但是最快的解决方案只需要0.14秒来计算我无法弄清楚他/她是如何做到的.与使用unordered_map相比,解决此问题的更快捷方法是什么？

unordered_map < int, string > words;    
int n;    
cin >> n;  
for (int i = 0; i < n; i++) {    
    string word;    
    int position;     
    cin >> word >> position;    
    words[position] = word;    
}    
for (int i = 1; i <= n; i++) {     
    cout << words[i] << "\n";      
} 

Answer 1

std::unordered_map这个问题有点过分了.由于提供了元素所在的顺序,因此您可以使用a std::vector<std::string>,而只需将元素放在输入告诉您的向量中.这简化了程序代码

int main()
{
    int records;
    std::cin >> records;
    std::vector<std::string> sentence(records);
    std::string word;
    int place;
    while (std::cin >> word >> place)
        sentence[place - 1] = std::move(word); // subtract one as input is 1 based index, use move to save an allocation and copy
    for (auto const& e : sentence)
        std::cout << e << " ";
}