P1918 保龄球

这道题也是很简单的~可手写hash，也可以直接用unordered_map,为什么不用map呢，因为map的效率太低了，map里面是红黑树，会自动排序，和set一样

但是unordered_map就是用hash实现的，非常方便~

先来说下区别：

排序
map: 在缺省下，按照递增的排序顺序
unordered_map :不排序

执行实施
map :在map内部采用了自平衡的BST（二叉搜索树）的数据结构，实现了数据排序
unordered_map: 内部采用了哈希表的数据结构

搜索时间：
map： 该类型的搜索时间复杂度为log(n)
unordered_map ： 搜索时间复杂度。O(1)为平均时间，最坏情况下的时间复杂度为O（n）;

插入操作的时间复杂度：
map : 该操作的时间 复杂度为log(n)+再平衡时间
unordered_map : 该操作的时间复杂度与搜索的时间复杂度一样。

删除操作的时间复杂度与插入操作的时间复杂度是一样的。
如果你想要一个具有排序后的数据的话，通常可以选择Map这种类型。或者想要打印具有一定顺序的元素。

下面是AC代码~

#include 
#include 
#include 
using namespace std;
unordered_map <int ,int > t;int main(){int n,Q,m;cin>>n;for(int i=1;i<=n;i++){int x;cin>>x;t[x]=i;//第i个球的位置为x}cin>>Q;for(int i=1;i<=Q;i++){cin>>m;cout<<t[m]<<endl;}return 0;}

下面两张图分别是map 和 unordered_map的AC时间，看官可以对比一下,unordered_map明显更快~

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！