y******6
发帖数: 49 | 1 Provide a data structure that can perform :
1. insert
2. delete
3. find min
4,. find max
5. delete min
6. delete max
all in O(1) time.
前面四个操作还好说，用一个hashtable和min stack, max stack就可以实现O(1)操作
，关键是operations 5&6，如果remove掉最小或者最大的元素，如何能找到second
smallest和second largest的元素？大牛们给一下提示？ ^__^ |
p*****2
发帖数: 21240 | 2
前边4个你说的方法可以O(1)吗？
【在 y******6 的大作中提到】
: Provide a data structure that can perform :
: 1. insert
: 2. delete
: 3. find min
: 4,. find max
: 5. delete min
: 6. delete max
: all in O(1) time.
: 前面四个操作还好说，用一个hashtable和min stack, max stack就可以实现O(1)操作
: ，关键是operations 5&6，如果remove掉最小或者最大的元素，如何能找到second
|
y******6
发帖数: 49 | 3
可以吧。拿findmin来说，有一个min stack,栈顶存的是当前所有元素的最小值。每次
insertion的时候，新的元素跟栈顶的元素比较,如果小于栈顶元素，push进栈，否则只
是插入到hash表中就可以了。delete元素的时候，被delete的元素跟栈顶的元素比较，
如果比栈顶的大，那么只将元素从hash表中delete即可，否则还要minstack.pop().
【在 p*****2 的大作中提到】
:
: 前边4个你说的方法可以O(1)吗？
|
p*****2
发帖数: 21240 | 4
insert和delete的复杂度多少？
【在 y******6 的大作中提到】
:
: 可以吧。拿findmin来说，有一个min stack,栈顶存的是当前所有元素的最小值。每次
: insertion的时候，新的元素跟栈顶的元素比较,如果小于栈顶元素，push进栈，否则只
: 是插入到hash表中就可以了。delete元素的时候，被delete的元素跟栈顶的元素比较，
: 如果比栈顶的大，那么只将元素从hash表中delete即可，否则还要minstack.pop().
|
y******6
发帖数: 49 | 5
insert和delete用hash的话，应该是O(1)吧。每次insert或者delete的时候维持min
stack和max stack的复杂度也是O(1)
【在 p*****2 的大作中提到】
:
: insert和delete的复杂度多少？
|
A*****i
发帖数: 3587 | 6 前四个要是O(1)了后俩就不能O(1)
如果要后俩O(1)必须在insert 和 delete的时候排序
想不出更好的法子了，呼唤高人 |
p*****2
发帖数: 21240 | 7
牛。
【在 y******6 的大作中提到】
:
: insert和delete用hash的话，应该是O(1)吧。每次insert或者delete的时候维持min
: stack和max stack的复杂度也是O(1)
|
y******6
发帖数: 49 | 8
deletemin 和deletemax要在O(1)时间内进行 肿木搞？
【在 p*****2 的大作中提到】
:
: 牛。
|
y******6
发帖数: 49 | 9
同问
【在 A*****i 的大作中提到】
: 前四个要是O(1)了后俩就不能O(1)
: 如果要后俩O(1)必须在insert 和 delete的时候排序
: 想不出更好的法子了，呼唤高人
|
s****n
发帖数: 48 | 10 如果这个ds存在，是不是sort可以在O(n)解决了？
insert, ... insert
findmin, deletemin,
findmin, deletemin
... |
|
|
y******6
发帖数: 49 | 11
是哦~~~ 帅气！
【在 s****n 的大作中提到】
: 如果这个ds存在，是不是sort可以在O(n)解决了？
: insert, ... insert
: findmin, deletemin,
: findmin, deletemin
: ...
|
c********t
发帖数: 5706 | 12 delete是只能delete most recent insert吗？
【在 y******6 的大作中提到】
:
: 是哦~~~ 帅气！
|
y******6
发帖数: 49 | 13
应该是任意一个元素吧 所以肯定会有hash吧
【在 c********t 的大作中提到】
: delete是只能delete most recent insert吗？
|
d**********x
发帖数: 4083 | 14 insert 6 3 1 2
delete 1
【在 y******6 的大作中提到】
:
: 应该是任意一个元素吧 所以肯定会有hash吧
|
l****i
发帖数: 2772 | 15 你这个还是有点问题吧。如果minstack被pop为空了，就出错了吧。
【在 y******6 的大作中提到】
:
: 应该是任意一个元素吧 所以肯定会有hash吧
|
y******6
发帖数: 49 | 16
如果minstack为空的话，那么存储所有元素的hash表也是空的
【在 l****i 的大作中提到】
: 你这个还是有点问题吧。如果minstack被pop为空了，就出错了吧。
|
l****i
发帖数: 2772 | 17 incoming: 1,3,2
Hash: 1,3,2
Minstack: 1
Maxstack: 1,3
delete 1或者delete 3
这样是不是就有问题了？难道我理解错了？
【在 y******6 的大作中提到】
:
: 如果minstack为空的话，那么存储所有元素的hash表也是空的
|
b**m
发帖数: 1466 | |
y******6
发帖数: 49 | 19
这个方法跟150题上的那个min stack是类似的，只适用于findmix或者findmax。
你说的这个情况是deletemin或者deletemax。我不知道怎么做，不过看10楼网友的分析
，我觉得这道题在O(1)时间复杂度下完成所有的操作是impossible的
【在 l****i 的大作中提到】
: incoming: 1,3,2
: Hash: 1,3,2
: Minstack: 1
: Maxstack: 1,3
: delete 1或者delete 3
: 这样是不是就有问题了？难道我理解错了？
|
h***i
发帖数: 1970 | 20 不对吧，如果我insert的是一个比当前最小值大，但是比其他都小，你不会把它push到
stack里，如果这时我delete min，后面再找min都是错误的。
【在 y******6 的大作中提到】
:
: 这个方法跟150题上的那个min stack是类似的，只适用于findmix或者findmax。
: 你说的这个情况是deletemin或者deletemax。我不知道怎么做，不过看10楼网友的分析
: ，我觉得这道题在O(1)时间复杂度下完成所有的操作是impossible的
|
|
|
c********t
发帖数: 5706 | 21 如果是任意一个，你的方法肯定不work啊，因为不是所有元素都入栈的。
试试连续运行下面的。
add 2 3
delete 2
getmin?
【在 y******6 的大作中提到】
:
: 这个方法跟150题上的那个min stack是类似的，只适用于findmix或者findmax。
: 你说的这个情况是deletemin或者deletemax。我不知道怎么做，不过看10楼网友的分析
: ，我觉得这道题在O(1)时间复杂度下完成所有的操作是impossible的
|
y******6
发帖数: 49 | 22
好像是的......
该用什么数据结构呢？
【在 c********t 的大作中提到】
: 如果是任意一个，你的方法肯定不work啊，因为不是所有元素都入栈的。
: 试试连续运行下面的。
: add 2 3
: delete 2
: getmin?
|
e***s
发帖数: 799 | 23 我不懂了
按楼主说的一个HashMap,一个MinStack,一个MaxStack
deleteMin的时候，不就是map.remove(MinStack.pop())吗？
下一个最小的不就在MinStack.peek（）吗？
要判断的是如果MinStack和MaxStack都只剩一个元素了（第一个插入的元素会push到两
个Stack中），要两个Stack都pop。 |
