f*******w 发帖数: 1243 | 1 Assuming that you are only allowed a constant amount of time for
initialization, design a representation for a table that allows one to
search, insert, and delete values in worst case time O(1), assuming that
each value is in the range 1 to m.
You may assume that no more than n insertions will be done and, that m+n + c
units of
space are available for you to use, where c is a small constant of your
choosing (e.g. 3 or 4).
Note that in this problem m and n are problem inputs, hence they are not
constants, hence initializing the entire space is not allowed, since that
would require time O(m+n).
我开始想的是初始化一个m维数组存个数……但人家说了m不是常数,不能直接这样分配 | l*****a 发帖数: 14598 | 2 fast search ==>hashtable
easy to insert/delete ==> linked list
use the two DS together may work for your case
c
【在 f*******w 的大作中提到】 : Assuming that you are only allowed a constant amount of time for : initialization, design a representation for a table that allows one to : search, insert, and delete values in worst case time O(1), assuming that : each value is in the range 1 to m. : You may assume that no more than n insertions will be done and, that m+n + c : units of : space are available for you to use, where c is a small constant of your : choosing (e.g. 3 or 4). : Note that in this problem m and n are problem inputs, hence they are not : constants, hence initializing the entire space is not allowed, since that
| f*******w 发帖数: 1243 | 3
hash table with n entries? each entry is a link list? (insert/delete the
same number?)
sounds good:)
【在 l*****a 的大作中提到】 : fast search ==>hashtable : easy to insert/delete ==> linked list : use the two DS together may work for your case : : c
| w****x 发帖数: 2483 | 4
hash table的桶数量也要根据元素个数调整啊, 要么初始化不是O(1), 要么insert的时
候不是O(1), 不知道这题要干什么?
【在 l*****a 的大作中提到】 : fast search ==>hashtable : easy to insert/delete ==> linked list : use the two DS together may work for your case : : c
| l***e 发帖数: 6 | 5 插入A[i]=k B[k]=m ++k
查找 A[i]
删除 在就B[A[i]]=-1
c
【在 f*******w 的大作中提到】 : Assuming that you are only allowed a constant amount of time for : initialization, design a representation for a table that allows one to : search, insert, and delete values in worst case time O(1), assuming that : each value is in the range 1 to m. : You may assume that no more than n insertions will be done and, that m+n + c : units of : space are available for you to use, where c is a small constant of your : choosing (e.g. 3 or 4). : Note that in this problem m and n are problem inputs, hence they are not : constants, hence initializing the entire space is not allowed, since that
| a*******y 发帖数: 1040 | 6 LRU like design?
hashtable + linkedlist |
|