f*****w 发帖数: 2602 | 1 本版历史里面的 没看到有答案的说
design a data structure, this data structure have four functions: pop,
push, min, top. DO NOT use any stack, queue, list, array or things like
this.
我不太明白如果list array都不能用的话 还能怎么实现? | n********y 发帖数: 66 | 2 use balanced trees ?
【在 f*****w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 本版历史里面的 没看到有答案的说 : design a data structure, this data structure have four functions: pop, : push, min, top. DO NOT use any stack, queue, list, array or things like : this. : 我不太明白如果list array都不能用的话 还能怎么实现?
| d*******l 发帖数: 338 | 3 看操作是典型的优先队列,一般可以用堆实现。虽说平时heap也多用数组实现,但应该
也能用二叉树
【在 f*****w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 本版历史里面的 没看到有答案的说 : design a data structure, this data structure have four functions: pop, : push, min, top. DO NOT use any stack, queue, list, array or things like : this. : 我不太明白如果list array都不能用的话 还能怎么实现?
| m**q 发帖数: 189 | 4 对时间复杂度有要求么?
(用stack+array可以在O(1)实现所有操作,不过题目不允许...)
【在 f*****w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 本版历史里面的 没看到有答案的说 : design a data structure, this data structure have four functions: pop, : push, min, top. DO NOT use any stack, queue, list, array or things like : this. : 我不太明白如果list array都不能用的话 还能怎么实现?
| d*******l 发帖数: 338 | 5 我好像想错了,第一眼看着像优先队列。。不过题目有点不清楚,pop应该有怎么样的
行为?是pop出最先push的还是最后push的元素?
【在 d*******l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 看操作是典型的优先队列,一般可以用堆实现。虽说平时heap也多用数组实现,但应该 : 也能用二叉树
| v*s 发帖数: 946 | 6 这个能详细说说嘛?
平时俺们用array实现的binary heap , push 只能做到O(logN)。
【在 m**q 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对时间复杂度有要求么? : (用stack+array可以在O(1)实现所有操作,不过题目不允许...)
| c*******n 发帖数: 63 | 7 我觉得design一个data structure的话,就不必拘泥于一般的stack需求
比如实现一个0和1的序列stack
pop就是返回最低有效位,并右移一位等
如
pop()
{
int ret = val & 1;
val >>= 1;
return ret;
}
反之
push(int i) // i=1 or i=0
{
val <<= 1;
val |= i;
} |
|