l***d
发帖数: 12 | 1 implement the class
初始的 number pool 包含 ［1...MAXLong］元素
checkout 返回number pool最小的元素，并取出
checkin 插入元素到number pool中
考虑只存checkout的元素，没太想清楚各种情况。。。
谁能说说最优的方案么 | j*****y
发帖数: 1071 | 2 难道不是用 min heap ?
interface NumberPool {
public long checkout();
public void checkin(long i);
}
implement the class
初始number pool contains ［1...MAXLong］
checkout 返回最小的元素
checkin 插入元素
考虑只存checkout的元素，没太想清楚各种情况。。。
谁能说说最优的方案么
还要发code 给他。。。在线等。。。
【在 l***d 的大作中提到】
: implement the class
: 初始的 number pool 包含 ［1...MAXLong］元素
: checkout 返回number pool最小的元素，并取出
: checkin 插入元素到number pool中
: 考虑只存checkout的元素，没太想清楚各种情况。。。
: 谁能说说最优的方案么
| r*******e
发帖数: 7583 | 3 用一个set保存已经checkout的元素，同时用变量m记录下一个被checkout的元素
checkin(i):
如果 i 不在set里，没有影响；
如果 i 在set里，set.remove(i), if (i < m) m = i;
checkout()
ret = m
m = 从set.upper_bound(m)开始找，下一个不在set里的
set.insert(ret)
return ret
【在 l***d 的大作中提到】
: implement the class
: 初始的 number pool 包含 ［1...MAXLong］元素
: checkout 返回number pool最小的元素，并取出
: checkin 插入元素到number pool中
: 考虑只存checkout的元素，没太想清楚各种情况。。。
: 谁能说说最优的方案么
| r*******e
发帖数: 7583 | 4 初始条件是所有的数都在pool里，直接用heap太占空间
【在 j*****y 的大作中提到】
: 难道不是用 min heap ?
:
: interface NumberPool {
: public long checkout();
: public void checkin(long i);
: }
: implement the class
: 初始number pool contains ［1...MAXLong］
: checkout 返回最小的元素
: checkin 插入元素
| l***d
发帖数: 12 | 5 checkout 元素很多后，还有improve的方法么？
【在 r*******e 的大作中提到】
: 用一个set保存已经checkout的元素，同时用变量m记录下一个被checkout的元素
: checkin(i):
: 如果 i 不在set里，没有影响；
: 如果 i 在set里，set.remove(i), if (i < m) m = i;
: checkout()
: ret = m
: m = 从set.upper_bound(m)开始找，下一个不在set里的
: set.insert(ret)
: return ret
| j******2
发帖数: 362 | 6 没有get it...是只要一直保存check in过的最小元素吗？那跟running min有啥区别呀
？干嘛要初始化呀？ | c*******i
发帖数: 30 | 7 Interval Tree
【在 l***d 的大作中提到】
: checkout 元素很多后，还有improve的方法么？
| l***d
发帖数: 12 | 8 不是的， 初始的元素有 maxlong 个，checkout的元素可能再次checkin
【在 j******2 的大作中提到】
: 没有get it...是只要一直保存check in过的最小元素吗？那跟running min有啥区别呀
: ？干嘛要初始化呀？
| j******2
发帖数: 362 | | j******2
发帖数: 362 | 10 感觉这个是对的。。。
【在 c*******i 的大作中提到】
: Interval Tree
| r*******e
发帖数: 7583 | 11 具体说说吧
如果保存还没被checkout的元素
checkin的时候怎么merge interval
【在 c*******i 的大作中提到】
: Interval Tree
| b*****u
发帖数: 648 | | d*******y
发帖数: 27 | 13 不是很明白题意。如果元素唯一的话，就可以用bitmap啊。
如果初有maxlong个元素，那么就是大约有4billion个数。用个bitmap，4G/8=512M。
checkout的时候从最小的开始扫描，直到发现第一个存在的数，clear bit后返回。
checkin的时候直接找到相应的位置，set bit就好了。 | z****p
发帖数: 18 | 14
-The interval tree is a binary search tree where each node in the tree
stores a (key,value) pair: the key is the left end of an interval, and the
value is the right end.
-The interval tree for this problem is special in that the intervals are non
-overlapping.
-Initially, the tree only contain 1 node, the (1, MaxLong) pair.
-Check out value v: find the largest key that is smaller than v, look at its
value, assuming it looks like (k0,v0); if v0 is less than v, then v is not
in the pool, and the check out fails; otherwise, remove that node (interval)
and spilt the interval into two (k0, v-1), (v+1, v0), and insert them back
into the tree.
-Check in v: find two intervals: (a) the largest key that is smaller than v,
say (k0,v0), and (b) the smallest key that is larger than v, say (k1,v1),
in the interval tree (they are consecutive intervals for sure).
---if v < v0, then v is already in the pool, the check in can be ignored.
---else if v0 == v-1 && v+1 == k1, then merge (k0,v0) and (k1,v1) into (k0,
v1), by removing them from the tree and inserting back the merged interval
---else if v0 == v-1, update (k0,v0) to (k0,v)
---else if v+1 == k1, remove (k1,v1) from tree and insert back (v+1,v1)
---else, insert new node (v,v)
that's it.
【在 r*******e 的大作中提到】
: 具体说说吧
: 如果保存还没被checkout的元素
: checkin的时候怎么merge interval
|
|
