狗家电面

dennissyx 发表于 2018-10-19 04:35
第一题，不计设计数据结构成本的话，不就是哈希表，int->linkedlist?这样就是O(1)吧

同意您的做法， 每个int做一个range 的list， 给了int就把list返出来， 就是O(1)了

longest increase sequence in 数列。 返回数列还是长度

pandami 发表于 2018-10-19 06:11
第一题build时候把有overkap的存一组 找的时候binary search 然后loop有overlap的小组

来自一亩三分地官方 ...

worst case这样不是O(N)吗？

Oshino 发表于 2018/10/22 21:28:04
第一题我觉得标准解法应该是线段树。查询logn 没问题的

问题是segtree里面存什么

pandami 发表于 2018-10-24 09:46
问题是segtree里面存什么

segment tree里面的值 就是overlap的个数

bearxiong2017 发表于 2018-10-20 07:19
多谢楼主分享
可以问下楼主三角形那题的思路吗
Range那题除了大家说的hashmap，我觉得也可以按begin排序 ...

不是，这样的worst是O(N)