t********e
发帖数: 344 | 1 how to design a queue, in addition to insert(), delete(), also has a
function min() which returns the minumum element? Can you do all functions
in O(1) time?
careercup上有一道关于stack的类似的题，很容易就做到O(1)了，但是这个queue的比
较难想……
请大虾赐教…… |
S******t
发帖数: 151 | 2 Just use two stacks to implement the queue. |
s******n
发帖数: 3946 | 3 keep another queue V.
when append a new element to queue, pops elements from V's end until find
element is less or equal than the new one, then append new element to the
end of V.
when remove first element from the queue, if front item of V is equal to the
first element of the queue, then remove first element of V.
the smallest element is the first element of V. |
s******n
发帖数: 3946 | 4 class DataStructure {
protected:
deque q;
deque v;
public:
void push_back(int data)
{
while (v.size()>0) {
if (v.back()>data) v.pop_back();
else break;
}
q.push_back(data);
v.push_back(data);
}
int pop_front() {
int ret = q.pop_front();
if (ret==v.front()) v.pop_front();
return ret;
}
int size() {
return q.size();
}
int minValue() {
assert(v.size()>0);
return v.front();
}
} |
p*****2
发帖数: 21240 | 5
the
不是要求0（1）吗
【在 s******n 的大作中提到】
: keep another queue V.
: when append a new element to queue, pops elements from V's end until find
: element is less or equal than the new one, then append new element to the
: end of V.
: when remove first element from the queue, if front item of V is equal to the
: first element of the queue, then remove first element of V.
: the smallest element is the first element of V.
|
t********e
发帖数: 344 | 6 这个“pops elements from V's end until find
element is less or equal than the new one”
不是O(n)了么
the
【在 s******n 的大作中提到】
: keep another queue V.
: when append a new element to queue, pops elements from V's end until find
: element is less or equal than the new one, then append new element to the
: end of V.
: when remove first element from the queue, if front item of V is equal to the
: first element of the queue, then remove first element of V.
: the smallest element is the first element of V.
|
s******n
发帖数: 3946 | 7 看怎么理解阿，插入N个元素操作的过中，V最多push N次，pop N次，平分到N个元素每个元素还是O(1)
【在 p*****2 的大作中提到】
:
: the
: 不是要求0（1）吗
|
t********e
发帖数: 344 | 8 这样delete()就是O（n）吧
【在 S******t 的大作中提到】
: Just use two stacks to implement the queue.
|
S******t
发帖数: 151 | 9 No, delete() is still amortized O(1)
【在 t********e 的大作中提到】
: 这样delete()就是O（n）吧
|
o*o
发帖数: 5155 | 10 从来没听说过big O可以平分的。
每个元素还是O(1)
【在 s******n 的大作中提到】
: 看怎么理解阿，插入N个元素操作的过中，V最多push N次，pop N次，平分到N个元素每个元素还是O(1)
|
|
|
s******o
发帖数: 2233 | 11 use a double-linked list L
for insert, if it's smaller than end of L, append to L;
for delete, if it's same as front of L, remove front of L;
for min, return end of L.
【在 t********e 的大作中提到】
: how to design a queue, in addition to insert(), delete(), also has a
: function min() which returns the minumum element? Can you do all functions
: in O(1) time?
: careercup上有一道关于stack的类似的题，很容易就做到O(1)了，但是这个queue的比
: 较难想……
: 请大虾赐教……
|
z*********8
发帖数: 2070 | 12 经典教材<算法导论>上面就有这章 amortized analysis
现在听说过了吧
【在 o*o 的大作中提到】
: 从来没听说过big O可以平分的。
:
: 每个元素还是O(1)
|
g**x
发帖数: 373 | 13 This has a problem:
For example,
Queue: 4 3 2 5 9 8 4
Double List: 4 3 2
After 3 deletion (4 3 2), the double list contains no min value of Queue.
【在 s******o 的大作中提到】
: use a double-linked list L
: for insert, if it's smaller than end of L, append to L;
: for delete, if it's same as front of L, remove front of L;
: for min, return end of L.
|
d*l
发帖数: 1810 | 14 不错
【在 s******n 的大作中提到】
: class DataStructure {
: protected:
: deque q;
: deque v;
: public:
: void push_back(int data)
: {
: while (v.size()>0) {
: if (v.back()>data) v.pop_back();
: else break;
|
m*****P
发帖数: 1331 | 15 别乱说话 ...
【在 o*o 的大作中提到】
: 从来没听说过big O可以平分的。
:
: 每个元素还是O(1)
|
w*****g
发帖数: 3 | 16 我来试一下看对不对。。。
队列+链表
队列就是正常存储的数据， FIFO， 只不过队列中的数据要额外多添加一个指针域， 指向其在链表对应的位置，
入队： 如果新加入的数比链表首要小或者相等（注意相等的细节），添加该数值到队列尾部和链表的首部，在队列中的那个指针指向其在链表中的位置；否则，指针设置为空就好了
出队： 如果要出队列的数值与链表头部的一样大（这种情况下对应的指针域不为空），同时删除链表首部的数据（通过指针）和出队列，否则，只出队列
最小： 就在链表首部
不知道讲清楚了没有。。。 |
t********e
发帖数: 344 | 17 clear to me
指向其在链表对应的位置，
队列尾部和链表的首部，在队列中的那个指针指向其在链表中的位置；否则，指针设置
为空就好了
），同时删除链表首部的数据（通过指针）和出队列，否则，只出队列
【在 w*****g 的大作中提到】
: 我来试一下看对不对。。。
: 队列+链表
: 队列就是正常存储的数据， FIFO， 只不过队列中的数据要额外多添加一个指针域， 指向其在链表对应的位置，
: 入队： 如果新加入的数比链表首要小或者相等（注意相等的细节），添加该数值到队列尾部和链表的首部，在队列中的那个指针指向其在链表中的位置；否则，指针设置为空就好了
: 出队： 如果要出队列的数值与链表头部的一样大（这种情况下对应的指针域不为空），同时删除链表首部的数据（通过指针）和出队列，否则，只出队列
: 最小： 就在链表首部
: 不知道讲清楚了没有。。。
|
w****o
发帖数: 2260 | 18 你的这个有点儿问题，
比如队列
头 3 8 5 尾
链表: 3
如果3从队列里出队后，链表就成空了。这就不对了。链表应该是5
指向其在链表对应的位置，
队列尾部和链表的首部，在队列中的那个指针指向其在链表中的位置；否则，指针设置
为空就好了
），同时删除链表首部的数据（通过指针）和出队列，否则，只出队列
【在 w*****g 的大作中提到】
: 我来试一下看对不对。。。
: 队列+链表
: 队列就是正常存储的数据， FIFO， 只不过队列中的数据要额外多添加一个指针域， 指向其在链表对应的位置，
: 入队： 如果新加入的数比链表首要小或者相等（注意相等的细节），添加该数值到队列尾部和链表的首部，在队列中的那个指针指向其在链表中的位置；否则，指针设置为空就好了
: 出队： 如果要出队列的数值与链表头部的一样大（这种情况下对应的指针域不为空），同时删除链表首部的数据（通过指针）和出队列，否则，只出队列
: 最小： 就在链表首部
: 不知道讲清楚了没有。。。
|
w*****g
发帖数: 3 | 19 恩 还是个大问题。。。进入胡同了。。。 谢谢提出问题！
开始倾向于上面均摊分析的方法了。。。
【在 w****o 的大作中提到】
: 你的这个有点儿问题，
: 比如队列
: 头 3 8 5 尾
: 链表: 3
: 如果3从队列里出队后，链表就成空了。这就不对了。链表应该是5
:
: 指向其在链表对应的位置，
: 队列尾部和链表的首部，在队列中的那个指针指向其在链表中的位置；否则，指针设置
: 为空就好了
: ），同时删除链表首部的数据（通过指针）和出队列，否则，只出队列
|
a*****s
发帖数: 1121 | 20 保留原始FIFO队列，再要一个栈，专门存最小值。
第一个元素直接进栈，后面来一个元素，跟栈顶比大小，大的不管，小于等于的进
栈顶。
min的时候直接取栈顶。队列delete（）的时候要检查是否是最小元素，若是则栈
也pop一个，保持同步。
没说不让用栈啊。 |
|
|
s******n
发帖数: 3946 | 21 Wrong:
add
5,4,3,6,7
your stack is 5, 4, 3
then remove
5,4,3
your stack is
5, 4
min() return 4, which is wrong, should return 6
【在 a*****s 的大作中提到】
: 保留原始FIFO队列，再要一个栈，专门存最小值。
: 第一个元素直接进栈，后面来一个元素，跟栈顶比大小，大的不管，小于等于的进
: 栈顶。
: min的时候直接取栈顶。队列delete（）的时候要检查是否是最小元素，若是则栈
: 也pop一个，保持同步。
: 没说不让用栈啊。
|
j*****j
发帖数: 201 | 22 这不是一般的队列，这是双端队列，不合题意吧？
the
【在 s******n 的大作中提到】
: keep another queue V.
: when append a new element to queue, pops elements from V's end until find
: element is less or equal than the new one, then append new element to the
: end of V.
: when remove first element from the queue, if front item of V is equal to the
: first element of the queue, then remove first element of V.
: the smallest element is the first element of V.
|
t*****r
发帖数: 1 | 23 可不可以这么来做
用一个队列来保存数据(设为q)，一个环型数组保存最小值（设为v），环形数组有两个
指针，start和end
1. v刚开始为空，start=end=0, 设 v[start] = MAX
2. 如果此时入队列的元素为value， 如果value < v[end] 那么v[end]=value
3. 如果value >= v[end], 那么 v[++end] = value (由于是环形数组，需要对start
和end下标进行处理
4.遇到队列pop_front()的时候，只有当 q.top() == v[start] 才将 start++
用例子来说明，比如队列是 5,4,3,6,7
那么此时 v中是 3,6,7
pop出5,4的时候，队列中最小值是3， v[start]也是3
pop 3的时候 ，队列中最小值是6， v[start]也是6
不知道这种方法如何？
可以用deque来代替这个环形数组的实现 |
d*******a
发帖数: 21 | 24 正解，看编程之美里有这个的
【在 S******t 的大作中提到】
: Just use two stacks to implement the queue.
|
t**********h
发帖数: 2273 | 25 恩，很好的想法，每个node多一个min变量，压第一个盏的时候，检查top的min，决定
要压入的node的min。第一个盏往第二个盏灌的时候，同样的做法。
多谢。
【在 S******t 的大作中提到】
: Just use two stacks to implement the queue.
|
z********i
发帖数: 568 | 26 有细节吗？网上搜了一下，有些怀疑是否可能。
【在 d*******a 的大作中提到】
: 正解，看编程之美里有这个的
|
l********7
发帖数: 114 | 27 基于比较的sort算法，average最少需要O(nlogn)。
反证法：
假设存在这样一个queue, insert(), delete(), min() cost O(1).
then for a given unsorted numbers, we can first insert all numbers into the
queue. cost is O(n).
repeated use min() and delete(), we can get a sorted sequence of the
original numbers. the cost is O(n).
so to sort, the total cost is O(n). Contradiction. (qed) |
p****a
发帖数: 12 | 28
the
Note that queue is different from heap. delete() only removes the head, not
the minimum. So you cannot use this queue to sort.
【在 l********7 的大作中提到】
: 基于比较的sort算法，average最少需要O(nlogn)。
: 反证法：
: 假设存在这样一个queue, insert(), delete(), min() cost O(1).
: then for a given unsorted numbers, we can first insert all numbers into the
: queue. cost is O(n).
: repeated use min() and delete(), we can get a sorted sequence of the
: original numbers. the cost is O(n).
: so to sort, the total cost is O(n). Contradiction. (qed)
|
z******t
发帖数: 59 | 29 我有一篇博客讨论关于queue中最大值的问题：
http://codercareer.blogspot.com/2012/02/no-33-maximums-in-slidi
欢迎批评指正。
【在 t********e 的大作中提到】
: how to design a queue, in addition to insert(), delete(), also has a
: function min() which returns the minumum element? Can you do all functions
: in O(1) time?
: careercup上有一道关于stack的类似的题，很容易就做到O(1)了，但是这个queue的比
: 较难想……
: 请大虾赐教……
|
h****e
发帖数: 928 | 30 这位就是何海涛大牛啊。
【在 z******t 的大作中提到】
: 我有一篇博客讨论关于queue中最大值的问题：
: http://codercareer.blogspot.com/2012/02/no-33-maximums-in-slidi
: 欢迎批评指正。
|
|
|
z********i
发帖数: 568 | 31 queue and stack are different for min: (1) min of queue is dynamic,
depending on futher insertion of numbers, while (2) min of stack is "static"
--is determined by current numbers in stack.
For example：both queue and stack have numbers 10 20 30 40. Then the min of
both queue and stack are 10. However，after 5 is inserted, the min of the
queue is 5(min of 10 20 30 40 5), while the min of the stack is still 10(min
of 10, 20, 30, 40)
Now let look at one example for min using auxiliary stack to implement queue
with min. Assume 1,2,3,4 and 5 are inserted. Then the data queue has 1 2 3
4 5, and the auxiliary queue has 1 1 1 1 1. Now min returns 1 currently.
However, after deleting 1, the data queue has 2 3 4 5, and the auxiliary
queue has 1 1 1 1. Now the min returns incorrect vlaue 1, which should be 2.
It seems that the second approach for stack with min(by computing "min"
carefully) still not working because of the different of the min between
queue and stack.
【在 z******t 的大作中提到】
: 我有一篇博客讨论关于queue中最大值的问题：
: http://codercareer.blogspot.com/2012/02/no-33-maximums-in-slidi
: 欢迎批评指正。
|
z********i
发帖数: 568 | 32 The following algorithm for queue with max is correct to me:
http://www.sureinterview.com/wiki/Shwqst/903001
idea:
1 用数据队列保存所有数据X[0]，X[1]，...
2 用辅助队列保存数据中的X[i1],X[i2],etc. such that
2.1 X[i1]>=X[i2]>=...。
2.2 X[i1]是从X[i1]开始最大的数。
3 enque的时候,删除辅助队列中比要插入的数据小（<）的数据。
4 deque的时候，删除数据队列的第一个数据。同时，如果辅助队列的第一个数据等于数据队列的第一个数据，删除辅助队列的第一个数据。
5 max就是辅助队列的第一个数据
例子一。
数据队列：6 5 4。
辅助队列：6 5 4。
1) max: 辅助队列的第一个数据6.
2) deque：
数据队列：5 4。
辅助队列：5 4
max: 5
3) deque:
数据队列：4。
辅助队列：4
max: 4
例子二。
数据队列：4 5 6。
辅助队列：6。
1) max: 辅助队列的第一个数据6.
2) deque：
数据队列：5 6。
辅助队列：6
max: 6
3) deque:
数据队列：6。
辅助队列：6
max: 6
例子三。
数据队列：4 6 5。
辅助队列：6 5。
1) max: 辅助队列的第一个数据6.
2) deque：
数据队列：6 5。
辅助队列：6 5
max: 6
3) deque:
数据队列：5。
辅助队列：5
max: 5
复杂度：easy to see that O(1) for both deque and max.
enque: complexity is from the while loop(comparisons).
For some comparisons, each comparison corresponds to a deletion of an element from the auxiliary queue. Since each element can be deleted at most once from the auxiliary queue, such comparisons are in total O(n), thus amortized cost of O(1) per element insertion.
However, there are comparisons which do not correspond to deletion of elments from the auxiliary queue. For example, auxiliary queue has elements 6 5. when inserting 4, we compare 4 with 5. Since 5 not less than or equal to 4, 5 is not deleted from the auxiliary queue, though we have one comparison between 4 and 5. How many such comparisons withou deletion? An observation is that for each such comparison without deletion, we must insert an element into the auxiliary queue. So there are at most O(n) such comparisons without deletion, thus amortized cost of O(1) per element. |
y**********u
发帖数: 6366 | 33 把当前的min带着就行了
queue size double
【在 t********e 的大作中提到】
: how to design a queue, in addition to insert(), delete(), also has a
: function min() which returns the minumum element? Can you do all functions
: in O(1) time?
: careercup上有一道关于stack的类似的题，很容易就做到O(1)了，但是这个queue的比
: 较难想……
: 请大虾赐教……
|
z********i
发帖数: 568 | 34 swanswan described the same algorithm.
于数据队列的第一个数据，删除辅助队列的第一个数据。
【在 z********i 的大作中提到】
: The following algorithm for queue with max is correct to me:
: http://www.sureinterview.com/wiki/Shwqst/903001
: idea:
: 1 用数据队列保存所有数据X[0]，X[1]，...
: 2 用辅助队列保存数据中的X[i1],X[i2],etc. such that
: 2.1 X[i1]>=X[i2]>=...。
: 2.2 X[i1]是从X[i1]开始最大的数。
: 3 enque的时候,删除辅助队列中比要插入的数据小（<）的数据。
: 4 deque的时候，删除数据队列的第一个数据。同时，如果辅助队列的第一个数据等于数据队列的第一个数据，删除辅助队列的第一个数据。
: 5 max就是辅助队列的第一个数据
|
