我要招人

去企业版

首页 > 试题广场 >

下列容器中，哪些容器按 key 查找的复杂度为 O(log(

[不定项选择题]

下列容器中，哪些容器按key查找的复杂度为O(log(n)) ?

```
std::unordered_set
```
```
std::multimap
```
```
std::map
```
```
std::deque
```

查看正确选项

秋招加油o

STL库中，map和multimap底层都是红黑树实现的，两者的不同在于multimap允许重复的可以，而map中不行。

红黑树的查找复杂度为O(log(n))

unodered_map/_set底层是哈希表实现的，查找复杂度为O(1)

发表于 2019-09-06 15:19:43 回复(5)

努力找到工作，保持积极乐观

map 与 multimap是存储key-value（键-值对）类型的容器。

不同之处在于：map只允许key与 value一一对应；multimap一个key可对应多个value；

如上图所示

map

multimap可使用count(k)求出键值k的出现次数，find(k)返回第一个拥有K的的实例

multimap<int, int>::size_type cnt = testMap.count(searchItem);

multimap<int, int>::iterator iter = testMap.find(searchItem);

for(;cnt > 0; cnt--, iter++)

{

cout<<iter->first<<" "<<iter->second<<endl;

}

而且map和multimap都是由RB_tree（红黑树）来实现的，本就合适于查找，复杂度为 O( ln(N) )

UNordered_set ,unordered_map是由hash_table(哈希表)来实现的，时间复杂度为o(1)

deque的push_back, push_front, pop_back, pop_front操作时间复杂度为O(1)

发表于 2019-07-26 11:47:40 回复(1)

牛客257569856号

为什么java里面有你呀🙃

发表于 2020-04-30 12:19:21 回复(3)

IDEA2022.4.2

第一反应这是顺丰的题，这次打脸了🙄

发表于 2019-09-01 16:10:50 回复(0)

zzzzzqf

我蒙了，我以为已经菜到连java的题目都看不懂了

发表于 2020-07-10 09:55:17 回复(0)

牛客690035903号

跑错片场了吧，这里是java

发表于 2020-06-11 22:04:14 回复(0)

SaltWater_y

完美避开了正确答案😥

发表于 2019-10-11 23:51:51 回复(0)

牛油学习去

发表于 2023-12-07 19:13:40 回复(0)

美团内推（官方渠道）

<p>可是hashmap先由链表+数组实现，复杂度是o（1），感觉c选项map很不严谨</p>

发表于 2020-05-18 08:52:53 回复(1)

千眚无德

map和multimap底层都是由红黑树实现，不同点在于，multimap允许相同元素，而mao不允许相同元素。

编辑于 2024-03-06 15:30:10 回复(0)

无敌的佐菲倒下了

STL库中，map和multimap底层都是红黑树实现的，两者的不同在于multimap允许重复的可以，而map中不行。

红黑树的查找复杂度为O(log(n))

unodered_map/_set底层是哈希表实现的，查找复杂度为O(1)

发表于 2021-07-21 17:44:30 回复(0)

mshentai

unodered_map/unodered_set底层是哈希表实现的，查找复杂度为O(1)

发表于 2021-06-21 09:00:53 回复(0)

牛客536807034号

数据结构不牢，我自己面壁。

发表于 2020-10-03 01:15:38 回复(0)

牛客894571553号

选B C 选项；

unordered_set基于哈希表，数据插入和查找的时间复杂度很低，几乎是常数时间

map的底层实现为红黑树，查找效率比较高，是O(logN);
双端队列deque是每次取的队首的元素，所以查找速度很快，为常数

发表于 2020-08-12 11:46:17 回复(0)

ThinkingOverflow

有一说一，虽然这是C++的题放到java有点怪，但是大家应该都能看出这题在考数据结构的复杂度吧。

发表于 2020-03-27 01:34:21 回复(0)

汉寿周杰伦

STL库中，map和multimap底层都是红黑树实现的，两者的不同在于multimap允许重复的可以，而map中不行。红黑树的查找复杂度为O(log(n)) unodered_map/_set底层是哈希表实现的，查找复杂度为O(1)

发表于 2020-03-22 17:35:06 回复(0)

浅紫、彼岸花开

java应该是I(n)

发表于 2019-11-22 14:08:13 回复(0)

江晨硕

::归属，这是c++的题吧，map不应该是On么

发表于 2019-11-21 17:53:32 回复(0)

百思不得姐

这题是C++题，这块内容应该相当于JAVA中集合那块的内容吧，没有深入了解，这方面的大佬可以普及一下

发表于 2019-08-31 11:18:11 回复(0)

提交观点

问题信息

算法工程师复杂度旷视 2019 C++

上传者：小小

难度：

19条回答 1619收藏 7905浏览

下列容器中，哪些容器按 key 查找的复杂度为 O(log(

问题信息

热门推荐

相关试题