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 的大作中提到】
: 本版历史里面的 没看到有答案的说
: 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 的大作中提到】
: 本版历史里面的 没看到有答案的说
: 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 的大作中提到】
: 本版历史里面的 没看到有答案的说
: 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 的大作中提到】
: 看操作是典型的优先队列，一般可以用堆实现。虽说平时heap也多用数组实现，但应该
: 也能用二叉树
| v*s
发帖数: 946 | 6 这个能详细说说嘛？
平时俺们用array实现的binary heap ， push 只能做到O（logN）。
【在 m**q 的大作中提到】
: 对时间复杂度有要求么?
: (用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;
} |
|
