d****o
发帖数: 1055 | 1 构造数据结构，实现两个function
int getProcessID()
void freeProcessID(int id)
要求，如果getProcessID 调用6次，那么系统里面会有6个process在运行，(id 从 1到
6)如果,freeprocessid(x)调用，系统里面对应得process x会被释放。
但是，如果再一次调用getProcessID(), 会返回最小的之前被释放得processID.
举例:调用顺序:
getProcessID()
getProcessID()
getProcessID()
getProcessID()
getProcessID()
getProcessID()//系统里面会有6个process
free(5)//系统process 1,2,3,4,6
free(3)//系统process 1,2,4,6
free(6) //系统process 1,2,4
getProcessID() //系统process 1,2,3,4
getProcessID() //系统process 1,2,3,4,5
请问用什么数据结构实现，使得这两个function的运行时间都为O(1)? | C***U
发帖数: 2406 | 2 heap吧
用来保存释放掉的id
【在 d****o 的大作中提到】
: 构造数据结构，实现两个function
: int getProcessID()
: void freeProcessID(int id)
: 要求，如果getProcessID 调用6次，那么系统里面会有6个process在运行，(id 从 1到
: 6)如果,freeprocessid(x)调用，系统里面对应得process x会被释放。
: 但是，如果再一次调用getProcessID(), 会返回最小的之前被释放得processID.
: 举例:调用顺序:
: getProcessID()
: getProcessID()
: getProcessID()
| i******e
发帖数: 273 | 3 用两个deque, 一个存放当前最大的pid, 一个存放最小连续pid中最大的一个，就能实
现O(1)操作。 | A**u
发帖数: 2458 | 4 都是O(1)操作，好像比较拿实现。
先不说getProcessID,
就 说free过程，至多是O(lgN)吧
【在 d****o 的大作中提到】
: 构造数据结构，实现两个function
: int getProcessID()
: void freeProcessID(int id)
: 要求，如果getProcessID 调用6次，那么系统里面会有6个process在运行，(id 从 1到
: 6)如果,freeprocessid(x)调用，系统里面对应得process x会被释放。
: 但是，如果再一次调用getProcessID(), 会返回最小的之前被释放得processID.
: 举例:调用顺序:
: getProcessID()
: getProcessID()
: getProcessID()
| d****o
发帖数: 1055 | 5 这个不行，我就说用这个，但是当getprocessid之后，你还需要整理堆，是log(n)。
【在 C***U 的大作中提到】
: heap吧
: 用来保存释放掉的id
| d****o
发帖数: 1055 | 6 没看懂，能不能展开说说。
【在 i******e 的大作中提到】
: 用两个deque, 一个存放当前最大的pid, 一个存放最小连续pid中最大的一个，就能实
: 现O(1)操作。
| C***U
发帖数: 2406 | 7 没看见要o(1). 不好意思
这个不行，我就说用这个，但是当getprocessid之后，你还需要整理堆，是log(n)。
★ Sent from iPhone App: iReader Mitbbs 7.56 - iPad Lite
【在 d****o 的大作中提到】
: 这个不行，我就说用这个，但是当getprocessid之后，你还需要整理堆，是log(n)。
|
|
