勾勾店面

ooio 发表于 2020-07-26 23:03:37
我觉得这个思路是对的，对每次生成的数字n，检查n-1和n+1是否存在，如果存在则说明n与之相连；对于一个连续的序列，只把序列长度保存在首尾即可，不必update序列中间的值，所以是O(1)的复杂度。根

谢谢分享思路，但是这个答案好像会造成内存泄露。因为这样内存可能无限扩大。是不是要优化一下删除不需要的key

tczhaodachuan 发表于 2020-7-27 19:49
谢谢分享思路，但是这个答案好像会造成内存泄露。因为这样内存可能无限扩大。是不是要优化一下删除不需要 ...

这个不算是内存泄露吧，应该是空间复杂度为O(N)，N为next()调用的次数（也是generateNumber调用的次数）。
如果删除不需要的key，就不会是O(1)。同时，那些key也都是需要的，来判断generatedNumber是不是已经存在。

不就是union find吗，每次有新数字n，让n和n+1/n - 1 union起来， 然后看size[start number]

泡利不相容 发表于 2020-7-28 05:48
不就是union find吗，每次有新数字n，让n和n+1/n - 1 union起来， 然后看size[start number]

有什么O(1)的方法算size of group with startNum 吗？

djewssw 发表于 2020-7-25 02:50
没必要用map存interval，只要把当前的startNum和比startNum大的数存到一个set里面就行了。每次执行Next的时 ...

假如startNum = 1
set里面有连续的2-10w，那么next()就需要一直startNum++ 直到10w才能返回？

泡利不相容 发表于 2020-7-28 05:48
不就是union find吗，每次有新数字n，让n和n+1/n - 1 union起来， 然后看size[start n ...

我也觉得是union find

djmiss 发表于 2020-7-30 21:36
假如startNum = 1
set里面有连续的2-10w，那么next()就需要一直startNum++ 直到10w才能返回？

这跟之前提到的ArrayList扩容一样。假如你有一个长度10万的ArrayList，插入下一个的时候正好满了需要扩容。这时候需要移动10万个元素，但是它的amortized cost仍然是O(1)