求教这题lc 981 Time Based Key-Value Store 为啥TLE

ezohuya 发表于 2020-7-31 08:16
我都没反应过来你在用index操作LinkedList（那肯定有问题
add是amortized O(1) worst O(n)

谢谢回复! 不过第一句话是啥意思 没太懂。。。什么问题呢？

jygooooo 发表于 2020-7-31 08:19
谢谢回复! 不过第一句话是啥意思 没太懂。。。什么问题呢？

LinkedList是sequential access container不是random access container，
按index访问属于random access，LinkedList只能每次从头部帮你遍历到那个index位置上的元素所以get是O(n) (both average and worst)

ezohuya 发表于 2020-7-31 08:22
LinkedList是sequential access container不是random access container，
按index访问属于random access ...

get 谢谢！

jygooooo 发表于 2020-07-30 17:13:18
确实 谢谢！ 换了后可以过了。
不过换成ArrayList了后add的复杂度变成O（N）了  这个怎么解释呢。。猜测test  case里面get比set多？

这个add是加在队尾是O(1)啊，数据结构基础