Leetcode 432 All O`one 变种

Job Hunting Interview
, , ,
1

leetcode 432 All O`one Data Structure：

Implement a data structure supporting the following operations:
Inc(Key) - Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
Dec(Key) - If Key’s value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string “”.
GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string “”.
Challenge: Perform all these in O(1) time complexity.

这个题如果改成
inc(String key, int v); 每次增加v而不是增加1
dec(String key, int v); 每次减少v而不是减少1
其他方法不变，怎样实现全O(1) ？

2

这感觉需要根据v能够定位到相应的bucket

3

要做到时间上的O(1)的话，空间上要牺牲。
我相信你一开始是Bucket之间用指针连接，即next和prev。
可以进一步，产生很长的array，array里存放的是指向bucket的指针，array的index对应 count。Bucket之间连接的指针（即next和prev）还是保留。
inc(String key, int v) 后，新的 count（也就是+v以后的），可以在 array 里array[count]快速定位到相应的bucket。

4

另一种思路，就是建立一些哨兵bucket，比如是 100，200，300，400，500 。。。这些sentinel bucket可以是空的。这样可以根据 count 快速定位附近的哨兵bucket， 即 count / 100。哨兵bucket会有指针指向下一个存在的bucket。
同时可以track目前出现的count的最大值 max，这样哨兵bucket 的数量可以控制在 max 的范围内。

5

补充一下，这些哨兵bucket可以一开始先建好。预估一个大概的范围并全部先建好。