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 |
|
