面试官对我说containsKey的复杂度是O(n) ?

当时面试到手撕代码环节,写完了给面试官看,他问我这个算法的复杂度是多少,我说是O(n),他说你这用了containsKey,不是O(n^2)吗?我说不啊,containsKey的复杂度是O(1)并且解释了一下,结果面试官坚持说containsKey是要遍历的,复杂度就是O(n)blablabla……把我说的开始怀疑自己了,就没再坚持 ,于是面试到这儿就结束了。复盘面试的时候听录音听到这再次心生疑惑,于是查了下发现containsKey的时间复杂度确实就是O(1)呀……可惜我面试经验还是太少,当时怂了没敢怼他#面经#
全部评论
我好像被问过同样的问题(但不是美团)。我那时候回答的是正常情况下是O(1),您说的O(n)应该存在于极端情况下例如collision发生后并且因为hashcode的问题所有node都生成同样的hashcode并且处理collision时用的是链表,JDK 1.8后由于采用了红黑树所以当n大于8之后就算出现此类极端情况也只会是O(logn)。
1 回复 分享
发布于 2020-04-20 15:45
怎么算也算不出来O(n)啊,怼他,让他回去多读读源码😂
1 回复 分享
发布于 2020-04-20 15:34
大佬,这样的公司不值得你加入
点赞 回复 分享
发布于 2020-04-20 15:29

相关推荐

05-22 09:23
门头沟学院 Java
点赞 评论 收藏
分享
05-23 19:02
吉林大学 Java
点赞 评论 收藏
分享
评论
4
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务