狗狗家阳谷店面

请问楼主第四题是什么做法。

请问 lz 投的是什么职位哇？
大米已加

西法的洛 发表于 2019/08/15 14:25:08
请问 lz 投的是什么职位哇？
大米已加

应该就是general swe？

Wyf2222 发表于 2019/08/15 05:41:54
请问楼主第四题是什么做法。

嗯…我好像已经回答了一次 不过没关系。。
用bst 查找里面有没有元素和target value差值少于L的

第三题是不是dfs做 ?   min max 可能会导致不连续的range

branson821 发表于 2019-8-19 12:38
第三题是不是dfs做 ?   min max 可能会导致不连续的range

是用dynamic programming啦
如果你可以到第i个元素，你肯定是从其中以下几个地方过来的
i-1, i-min, i-min-1,..i-max

第四题我觉得也可以用一个长度是2k的sliding windows做。平移window的同时maintain一个ordered_map, 也就是插入新出现的数字，移除在window内出现次数等于0的数字。每移动一次，就检查map里最小的数的出现次数是不是>1,如果只出现一次的话就看比最小数大一点的那个数是不是和它的差值小于L; 同理对最大的数也是一样的处理方法。
这样做的时间复杂度是 O(n*log(k)), 空间复杂度是O（k）。
不知道有没有问题，欢迎指教。

KuanCNTF 发表于 2019/08/20 08:49:03
第四题我觉得也可以用一个长度是2k的sliding windows做。平移window的同时maintain一个ordered_map, 也就是插入新出现的数字，移除在window内出现次数等于0的数...

嗯！比如这样一个数组
1 5 3 2 7 2.5
k=3
L=0.5
从每一个数往后数k个 如果其中有差值小于L的就算重复的话 那么2和2.5就算是duplicate了
所以对于每一个数 可以算做duplicate的range是独立的（当然也有overlap的时候
用orderedmap的话 每次你比对当前的元素和map里的k个数 这个的时间复杂度是不是也要算进去？
构建维护map是 log(k)
同时查找map里面元素是否属于duplicate是k
然后数组长度是n
所以这样是nklog(k)？

Neko酱の假尾巴 发表于 2019-8-13 12:27
**** 本内容被作者隐藏 ****

分已经加~
求问楼主，构建/维护一个bst是不是等效于维护一个ordered_map？每次查找的时候都要把这个bst/ordered_map里的每一个元素都从小到大走一遍？
所以总的复杂度是n*（k+log（k））=n*k
这样对吗