勾勾店面

樱花节 发表于 2020-7-26 01:28
这个时间复杂度主要在处理startNum上，可能也不是O（1）？worst case可能要是O（size）size=setSize

每个操作的平均复杂度O(1)，这跟Hash Map/Hash Set/ArrayList的Add操作是O(1)复杂度是一个道理。

k加入， k-1 & k+1 分别存在，同时存在的三种情况下，怎么update 前后key的value，以及startNumber的value？

1. k-1 & k+1同时存在：
smaller = map.get(k-1);
bigger = map.get(k+1);
newLength = smaller + 1 + bigger;
map.put(k-1-smaller+1, newLength);
map.put(k+1+bigger-1, newLength);
map.put(k, 1);

2. k-1存在：
smaller = map.get(k-1);
newLength = smaller + 1;
map.put(k-1-smaller+1, newLength);
map.put(k, newLength);

3: k+1存在：
bigger = map.get(k+1);
newLength = bigger + 1;
map.put(k+1+bigger-1, newLength);
map.put(k, newLength);

You don't have to update start number's value unless start number is the end point of the interval you are merging with k. It's O(1) operation (guaranteed in worst case).

一个更直观的做法：
其实如果数字是有上限（如Integer.MAX_VALUE)的话，可以从startNum到上限这里建立一个DoubleLinkedList，一旦有新的数字进来就把它从DLL里kick off。这样每次只要返回startNum.next.val就可以了

匿名者 发表于 2020-7-25 03:25
从startNum开始，如果startNum+1也在set里面，就把startNum删掉，并且startNum++。
这个地方startNum++ ...

要是这么想基本上没有数据结构能做到O(1)了。

ArrayList/HashSet/HashMap在插入的时候都要扩容，但这些依然被认为是O(1)的复杂度(amortized complexity)

djewssw 发表于 2020-7-27 02:00
要是这么想基本上没有数据结构能做到O(1)了。

ArrayList/HashSet/HashMap在插入的时候都要扩容，但这 ...

仔细想了下，你这个确实是amortized O(1)的，在k次add number中，startNum最多要加k次

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

感觉这个是正解

alpaca1234 发表于 2020-7-27 08:58
感觉这个是正解

从startNum开始，如果startNum+1也在set里面，就把startNum删掉，并且startNum++。

光这一步就不是O(1)呀

比如说一开始是[4], 后来成了[4,6,7,8,9,10,..,100]，那此时来个5，就要O(N)才能回到101

这题我11月面试undergrad summer intern第一题也问到了，当时水平太差，其实只要hashset就行了。。。 后悔之前不知努力

现在做题不虚了不知道这个暑假有没有机会给我了

donnice 发表于 2020-7-27 09:58
光这一步就不是O(1)呀

比如说一开始是[4], 后来成了[4,6,7,8,9,10,..,100]，那此时来个5，就要O(N) ...

amortized O(1)

coronaking2020 发表于 2020-7-24 22:08
建一个HashMap，key是startNumber和generateNumber()生成的数，value是以这个key为start/end point interva ...

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

1. '''
   
2. 给一个start number, 这时候系统会时不时的call一个generateNumber()函数，产生一个整数，要求Implement Next()这个函数，返回目前没有被产生的最小的，start number之后的数。 Next()这个函数只能take一个参数，就是刚才generate的那个数。举例
   
3. startnum = 4
   
4. Next() -> 5
   
5. GenerateNumber() generate 2
   
6. Next() -> 5
   
7. GenerateNumber() generate 6
   
8. Next() -> 5
   
9. GenerateNumber() generate 5
   
10. Next() -> 7
    
11. '''
    
12. 
    
13. class Solution:
    
14.     def __init__(self, startNumber):
    
15.         self.start = startNumber
    
16.         self.interval = {self.start:1}
    
17.         
    
18.     def next(self, generatedNumber):
    
19.         if generatedNumber <= self.start:
    
20.             return self.start + self.interval[self.start]
    
21.         
    
22.         if (generatedNumber - 1) in self.interval and (generatedNumber + 1) in self.interval:
    
23.             totalLen = self.interval[generatedNumber-1] + self.interval[generatedNumber+1] + 1
    
24.             
    
25.             # update 1st & last
    
26.             self.interval[generatedNumber-self.interval[generatedNumber-1]] = self.interval[generatedNumber+self.interval[generatedNumber+1]] = totalLen
    
27.             self.interval[generatedNumber] = 1
    
28.         elif (generatedNumber - 1) in self.interval:
    
29.             self.interval[generatedNumber] = self.interval[generatedNumber-1] + 1
    
30.             self.interval[generatedNumber-self.interval[generatedNumber-1]] = self.interval[generatedNumber-1] + 1
    
31.         elif (generatedNumber + 1) in self.interval:
    
32.             self.interval[generatedNumber] = self.interval[generatedNumber+1] + 1
    
33.             self.interval[generatedNumber+self.interval[generatedNumber+1]] = self.interval[generatedNumber+1] + 1
    
34.         else:
    
35.             self.interval[generatedNumber] = 1
    
36.             
    
37.         return self.start + self.interval[self.start]
    
38. 
    
39. if __name__ == '__main__':
    
40.     s = Solution(4)
    
41.     print(s.next(2)) # 5
    
42.     print(s.next(6)) # 5
    
43.     print(s.next(5)) # 7
    
44. 
    
45.     print(s.next(8)) # 7
    
46.     print(s.next(9)) # 7
    
47.     print(s.next(10)) # 7
    
48. 
    
49.     print(s.next(7)) # 11
    

复制代码

补充内容 (2020-7-28 00:35):
在19行，应该同时check if generatedNumber exists in self.interval.