t**********s
发帖数: 930 | 1 下面的问题我想用哈希表解决，可不符合要求。怎么才能使时间为常数并不依赖集合的
大小呢？
Design an efficient data structure for representing a subset S of the
integers from 1 to n. The operations we wish to perform are these:
1. Select an integer i from the set and delete it.
2. Add an integer i to the set.
A mechanism must be provided to ignore a request to add integer i to S in
the case where S alrady contains i. The data structure must be such that the
time to select and delete an element and the time to add an element are
consta |
S*****n
发帖数: 227 | 2 为什么hash table不符合要求？
the
【在 t**********s 的大作中提到】
: 下面的问题我想用哈希表解决，可不符合要求。怎么才能使时间为常数并不依赖集合的
: 大小呢？
: Design an efficient data structure for representing a subset S of the
: integers from 1 to n. The operations we wish to perform are these:
: 1. Select an integer i from the set and delete it.
: 2. Add an integer i to the set.
: A mechanism must be provided to ignore a request to add integer i to S in
: the case where S alrady contains i. The data structure must be such that the
: time to select and delete an element and the time to add an element are
: consta
|
t**********s
发帖数: 930 | 3 以为哈希表查找时有冲突，所以查找的时间不为常量啊
【在 S*****n 的大作中提到】
: 为什么hash table不符合要求？
:
: the
|
S*****n
发帖数: 227 | 4 建个n大小的hash table, 用==做hash函数。
有冲突就是存在啊。
【在 t**********s 的大作中提到】
: 以为哈希表查找时有冲突，所以查找的时间不为常量啊
|
t**********s
发帖数: 930 | 5 你是说哈希表的大小就是1...n的大小，就是subset S包含了所有1到n?
不是说哈希表是一个大集合影射到一个小集合上吗？
【在 S*****n 的大作中提到】
: 建个n大小的hash table, 用==做hash函数。
: 有冲突就是存在啊。
|
t****t
发帖数: 6806 | 6 没说小集合一定比大集合小啊
【在 t**********s 的大作中提到】
: 你是说哈希表的大小就是1...n的大小，就是subset S包含了所有1到n?
: 不是说哈希表是一个大集合影射到一个小集合上吗？
|
t**********s
发帖数: 930 | 7 那么下面的mechanism又是什么呢？
A mechanism must be provided to ignore a request to add integer i to S in
the case where S alrady contains i.
是不是这样就可以了：
if A(h(i))!=empty then return error
如果小集合与大集合相等，那么这个哈希表的具体实现就用arrar怎么样？
【在 t****t 的大作中提到】
: 没说小集合一定比大集合小啊
|
t*******t
发帖数: 6 | |
S*****n
发帖数: 227 | 9 一般的说，算法这个东西就是时间和空间搞trade-off, 在这个例子里，你想达到
常数时间的速度，你就的在空间上做牺牲，用足够大的空间。
【在 t**********s 的大作中提到】
: 那么下面的mechanism又是什么呢？
: A mechanism must be provided to ignore a request to add integer i to S in
: the case where S alrady contains i.
: 是不是这样就可以了：
: if A(h(i))!=empty then return error
: 如果小集合与大集合相等，那么这个哈希表的具体实现就用arrar怎么样？
|
S*****n
发帖数: 227 | 10 bitset太language specific了，只适用于C/C++。算法的东西，稍微general一点好。
【在 t*******t 的大作中提到】
: how about bitset?
|
t*******t
发帖数: 6 | 11 bitset is used in java too |
k*k
发帖数: 508 | 12 算法的实现都是 language specific 的吧
bitmap 换个角度看也就是另外一种 hash table
【在 S*****n 的大作中提到】
: bitset太language specific了，只适用于C/C++。算法的东西，稍微general一点好。
|
o**p
发帖数: 5 | 13 怯生生问一下，直接用大小为n+1得数组行不？
好像我没搞懂题意。
the
【在 t**********s 的大作中提到】
: 下面的问题我想用哈希表解决，可不符合要求。怎么才能使时间为常数并不依赖集合的
: 大小呢？
: Design an efficient data structure for representing a subset S of the
: integers from 1 to n. The operations we wish to perform are these:
: 1. Select an integer i from the set and delete it.
: 2. Add an integer i to the set.
: A mechanism must be provided to ignore a request to add integer i to S in
: the case where S alrady contains i. The data structure must be such that the
: time to select and delete an element and the time to add an element are
: consta
|
t**********s
发帖数: 930 | 14 我觉得行，n的数组就可以。因为只有n个元素。你也在上数据结构？
【在 o**p 的大作中提到】
: 怯生生问一下，直接用大小为n+1得数组行不？
: 好像我没搞懂题意。
:
: the
|
