大家都裸睡嘛？# Fashion - 美丽时尚
x*0
1 楼
下面这道题是在版上看到的一道题。请问大家有什么想法吗？
设计一个Map，满足下面的时间复杂度。
add: O(1) deletion: O(1) lookup: O(1) clear:O(1) iterate: O(number of
elements)。
提示：
如果我们用randomly accessed array，复杂度如下：
add: O(1) deletion: O(1) lookup: O(1) clear: O(size of array) iterate:
O(size of array)
如果我么用sequential array, 复杂度如下：
add: O(1) deletion: O(number of elements) lookup:O(number of elements)
clear: O(1) iterate:O(number of elements)
所以我们需要把这两个方法整合起来。
对于这题的提示，sequential array指的就是link list? 把每一对
randomly accessed array 是说可以直接用中的第一个Integer 作
为index吗？
设计一个Map
add: O(1) deletion: O(1) lookup: O(1) clear:O(1) iterate: O(number of
elements)。
提示：
如果我们用randomly accessed array，复杂度如下：
add: O(1) deletion: O(1) lookup: O(1) clear: O(size of array) iterate:
O(size of array)
如果我么用sequential array, 复杂度如下：
add: O(1) deletion: O(number of elements) lookup:O(number of elements)
clear: O(1) iterate:O(number of elements)
所以我们需要把这两个方法整合起来。
对于这题的提示，sequential array指的就是link list? 把每一对
randomly accessed array 是说可以直接用
为index吗？
