Yelp电面跪经，感觉被烙印黑了

delly224 发表于 2016-10-27 05:05
楼主您好，我想的是sort之后遍历，请问map怎么做？

我觉得如果只是要求数字连续而位置可以不连续，那么可以存进hashmap以后，对每个数,看看这个数是不是sequence的最小数，如果是的话就往上找。

physheng 发表于 2016-10-27 05:36
我觉得如果只是要求数字连续而位置可以不连续，那么可以存进hashmap以后，对每个数,看看这个数是不是sequ ...

没听懂，能举个例子吗

delly224 发表于 2016-10-27 05:41
没听懂，能举个例子吗

比如上面的例子，我们要从48，或者99开始找，因为98和47不在hashmap里面。

这个题dp做n^2 贪心做 nlogn 如果非要o(n)的话 可以做一个双端队列 和一个（value， index）的structure 然后按照value的大小从两端push进去 然后deque遍历一遍 把index错位的删掉 然后求长度

LC128                                                                        

做法是hashmap存数字，然后遍历一遍，对于X，如果X-1不在hashmap里面，那就一个个加一往上找，就是极大值。复杂度是O(n)。

楼主当时强行装逼要写一个single traversal一边建hashmap一边处理的，其实是可以写的但是容易出问题还不好理解，然后就装逼失败了= =

可以考慮用treemap, keyset() 輸出便會自動照順序 log(n)

UpDownDOTA 发表于 2016-10-27 10:06
做法是hashmap存数字，然后遍历一遍，对于X，如果X-1不在hashmap里面，那就一个个加一往上找，就是极大值。 ...

如果 n = 1 , 1024
你卻要跑到1024
這方法應該是O( max(n) )

这不是并查集做么

hohohw 发表于 2016-11-1 20:08
如果 n = 1 , 1024
你卻要跑到1024
這方法應該是O( max(n) )

找不到2，就停了。