b*********n
发帖数: 1258 | 1 You have a data structure of integers, which can be negative, zero, or
positive, and you need to support an API with two public methods, insert(int
) and getmedian(). Describe a data structure you would use to support this
API and describe the running time of the two methods. |
g*******y
发帖数: 1930 | 2 at first glance, use balanced BST like red-black tree can achieve
logN insert, and O(1) getmedian().
To achieve getmedian() in O(1), additional information might be added into tree node, like prev, next pointers
|
H*M
发帖数: 1268 | 3 a data structure augmented from red-black tree
also store the value in each node of the total number of elements of the
subtree (including that node itself)
insertion/deletion will be o(lgn)
getmedian will be o(lgn)
int
【在 b*********n 的大作中提到】
: You have a data structure of integers, which can be negative, zero, or
: positive, and you need to support an API with two public methods, insert(int
: ) and getmedian(). Describe a data structure you would use to support this
: API and describe the running time of the two methods.
|
H*M
发帖数: 1268 | 4 how can u getmedian by o(1)??
tree node, like prev, next pointers\
【在 g*******y 的大作中提到】
: at first glance, use balanced BST like red-black tree can achieve
: logN insert, and O(1) getmedian().
: To achieve getmedian() in O(1), additional information might be added into tree node, like prev, next pointers
:
|
b*********n
发帖数: 1258 | 5 有人说“The answer to the median question is to actually use two heaps, a
min heap and a max heap. Google for "median heap"”但不是很明白
int
【在 b*********n 的大作中提到】
: You have a data structure of integers, which can be negative, zero, or
: positive, and you need to support an API with two public methods, insert(int
: ) and getmedian(). Describe a data structure you would use to support this
: API and describe the running time of the two methods.
|
g*******y
发帖数: 1930 | 6 如果你的树中保持前驱后继指针
你每插一个数，Median要么不变，要么变成前驱，要么变成后继
【在 H*M 的大作中提到】
: how can u getmedian by o(1)??
:
: tree node, like prev, next pointers\
|
g*******y
发帖数: 1930 | 7 实质就是一个list和tree的混合啦
【在 g*******y 的大作中提到】
: 如果你的树中保持前驱后继指针
: 你每插一个数，Median要么不变，要么变成前驱，要么变成后继
|
b*********n
发帖数: 1258 | 8 Predecessor和Successor都需要O(log(n))时间来找吧
他们都是随时可能变化的
【在 g*******y 的大作中提到】
: 如果你的树中保持前驱后继指针
: 你每插一个数，Median要么不变，要么变成前驱，要么变成后继
|
g*******y
发帖数: 1930 | 9 你是说插入一个数之后，maintain 前驱后继的操作？我觉得是O(1)呢
你想，找插入位置，是利用树的性质，然后找到插入位置后，插入后maintain前驱后继的操作实质是一个双向链表的插入
【在 H*M 的大作中提到】
: how can u getmedian by o(1)??
:
: tree node, like prev, next pointers\
|
g*******y
发帖数: 1930 | 10 这个带前驱后继的BST，实际上也是一个双向链表
【在 b*********n 的大作中提到】
: Predecessor和Successor都需要O(log(n))时间来找吧
: 他们都是随时可能变化的
|
|
|
H*M
发帖数: 1268 | 11 我说的不是这个
我意思是你每insert一个新数，首先需要update各个元素的前驱后继吧。否则前驱后继
这些信息就错了。
要不你详细写下。可能我理解错了你意思。
【在 g*******y 的大作中提到】
: 你是说插入一个数之后，maintain 前驱后继的操作？我觉得是O(1)呢
: 你想，找插入位置，是利用树的性质，然后找到插入位置后，插入后maintain前驱后继的操作实质是一个双向链表的插入
|
g*******y
发帖数: 1930 | 12 你这样想啊，带前驱后继(按中序)的BST就是一个sorted的双向链表，你找到插入位置
后，在双向链表里插入一个元素，要多少时间？
不需要update每个数的前驱后继，只需要update O(1)个节点的前驱后继。 get it？
这个data structure好处就是把树跟链表结合在一起了，结合各自的优点
【在 H*M 的大作中提到】
: 我说的不是这个
: 我意思是你每insert一个新数，首先需要update各个元素的前驱后继吧。否则前驱后继
: 这些信息就错了。
: 要不你详细写下。可能我理解错了你意思。
|
H*M
发帖数: 1268 | 13 understood
挺高明！
【在 g*******y 的大作中提到】
: 你这样想啊，带前驱后继(按中序)的BST就是一个sorted的双向链表，你找到插入位置
: 后，在双向链表里插入一个元素，要多少时间？
: 不需要update每个数的前驱后继，只需要update O(1)个节点的前驱后继。 get it？
: 这个data structure好处就是把树跟链表结合在一起了，结合各自的优点
|
H*M
发帖数: 1268 | 14 其实我很想知道STL里面的ordered_map,是怎么实现的
应该是red_black tree,但是iterator++的话，输出successor(貌似O（1）),我怀疑是不是也加了这
种类似双向链表的东西。。
【在 H*M 的大作中提到】
: understood
: 挺高明！
|
g*******y
发帖数: 1930 | 15 嗯，这个方法其实很不错的，感觉比树+链表略好一些，空间的常数因子都更小
一点，时间上我不是很确定，但是猜测这个方法应该也能略好一些，因为不需要向RBT一样必须搜索到底部然后再旋转若干次来保持平衡。堆的一个优点就是本身就是平衡的了。的而且堆实现起来也比RBT容易很多很多。
关键就是在于保持小根堆和大根堆的size相差最多为1，
当某个堆的个数比另外一个堆多2个时，就需要移动一个到另外一个堆
而median始终是其中一个堆，或者两个堆的堆顶。
【在 b*********n 的大作中提到】
: 有人说“The answer to the median question is to actually use two heaps, a
: min heap and a max heap. Google for "median heap"”但不是很明白
:
: int
|
b*********n
发帖数: 1258 | 16 can u detail how to maintain their sizes differ only by 1?
RBT一样必须搜索到底部然后再旋转若干次来保持平衡。堆的一个优点就是本身就是平
衡的了。的而且堆实现起来也比RBT容易很多很多。
a
【在 g*******y 的大作中提到】
: 嗯，这个方法其实很不错的，感觉比树+链表略好一些，空间的常数因子都更小
: 一点，时间上我不是很确定，但是猜测这个方法应该也能略好一些，因为不需要向RBT一样必须搜索到底部然后再旋转若干次来保持平衡。堆的一个优点就是本身就是平衡的了。的而且堆实现起来也比RBT容易很多很多。
: 关键就是在于保持小根堆和大根堆的size相差最多为1，
: 当某个堆的个数比另外一个堆多2个时，就需要移动一个到另外一个堆
: 而median始终是其中一个堆，或者两个堆的堆顶。
|
g*******y
发帖数: 1930 | 17 如果B堆个数比A堆多了2
A.insert(B.extractTop());
【在 b*********n 的大作中提到】
: can u detail how to maintain their sizes differ only by 1?
:
: RBT一样必须搜索到底部然后再旋转若干次来保持平衡。堆的一个优点就是本身就是平
: 衡的了。的而且堆实现起来也比RBT容易很多很多。
: a
|
k***e
发帖数: 556 | 18 嗯 是空间换时间。增加2n个指针，将search time从lgn提高到常数
【在 g*******y 的大作中提到】
: 你这样想啊，带前驱后继(按中序)的BST就是一个sorted的双向链表，你找到插入位置
: 后，在双向链表里插入一个元素，要多少时间？
: 不需要update每个数的前驱后继，只需要update O(1)个节点的前驱后继。 get it？
: 这个data structure好处就是把树跟链表结合在一起了，结合各自的优点
|
k*k
发帖数: 49 | 19 i was asked this question
i proposed solution mentioned in this post except max+min heap.
seems max+min heap is the best solution....
sigh... wish i saw this post earlier....
in the end, they asked for the board-coding of a simpler getMedian() for a
collection in which the value of elements are constrained such as (1..100) |
z*f
发帖数: 293 | 20 找任意集合的MEDIAN?
【在 k*k 的大作中提到】
: i was asked this question
: i proposed solution mentioned in this post except max+min heap.
: seems max+min heap is the best solution....
: sigh... wish i saw this post earlier....
: in the end, they asked for the board-coding of a simpler getMedian() for a
: collection in which the value of elements are constrained such as (1..100)
|
|
|
b***e
发帖数: 1419 | 21 AVL tree, rotate after each insert, and the root is always the median.
insert(int
this
【在 b*********n 的大作中提到】
: You have a data structure of integers, which can be negative, zero, or
: positive, and you need to support an API with two public methods, insert(int
: ) and getmedian(). Describe a data structure you would use to support this
: API and describe the running time of the two methods.
|
H*M
发帖数: 1268 | 22 what do u mean "rotate after each insert"?
AVL tree, rotate after each insert, and the root is always the median.
insert(int
this
【在 b***e 的大作中提到】
: AVL tree, rotate after each insert, and the root is always the median.
:
: insert(int
: this
|
l*********b
发帖数: 1541 | 23 搞这么复杂，一个排序的数组不也可以：
o(logn) for insert
o(1) for median |
h***r
发帖数: 726 | 24 how to do inserting in log(N) in your case.
【在 l*********b 的大作中提到】
: 搞这么复杂，一个排序的数组不也可以：
: o(logn) for insert
: o(1) for median
|
b*********n
发帖数: 1258 | 25 what's the algorithm for your white-board getMedian() function?
Anything special?
heap or selection algo?
Thank you
【在 k*k 的大作中提到】
: i was asked this question
: i proposed solution mentioned in this post except max+min heap.
: seems max+min heap is the best solution....
: sigh... wish i saw this post earlier....
: in the end, they asked for the board-coding of a simpler getMedian() for a
: collection in which the value of elements are constrained such as (1..100)
|
t*********l
发帖数: 566 | |
c*********n
发帖数: 1057 | 27 不能说具体点么
【在 t*********l 的大作中提到】
: 算法作业题。。。
: 3m heap...
|
o********r
发帖数: 79 | 28 max+min是说把一半较小的元素放在max heap,另一半较大的放在min heap里么？
【在 k*k 的大作中提到】
: i was asked this question
: i proposed solution mentioned in this post except max+min heap.
: seems max+min heap is the best solution....
: sigh... wish i saw this post earlier....
: in the end, they asked for the board-coding of a simpler getMedian() for a
: collection in which the value of elements are constrained such as (1..100)
|
h*********e
发帖数: 56 | 29 AVL tree不能保证root是median吧？AVL tree 只是左右子树高度不差1，没说node
number 不差 1。除非设计自己的 descendant number self-balance BST。
我觉得任何整个排序的算法都做了额外的工作（包括black red tree, AVL tree, 和任
何形式的self-balancing binary search tree)。因为median只要比一半大，比一半小
就行了。至于两个一半里边是不是排好序的无所谓，只要找到最大最小就行了。这正是
heap的特点。
partial order 就行了， total order 没必要。所以我认为2个heap最好。
【在 b***e 的大作中提到】
: AVL tree, rotate after each insert, and the root is always the median.
:
: insert(int
: this
|
H*M
发帖数: 1268 | 30 ?
i remember it is for AVL tree too: the diff between the height of left and
right subtree of every node is at most 1.
RB is "at most twice"
【在 g*******y 的大作中提到】
: 如果B堆个数比A堆多了2
: A.insert(B.extractTop());
|
|
|
h*********e
发帖数: 56 | |
H*M
发帖数: 1268 | 32 u agree with blaze: using AVL tree can get the median by O(1)?
【在 g*******y 的大作中提到】
: 如果B堆个数比A堆多了2
: A.insert(B.extractTop());
|
H*M
发帖数: 1268 | 33 This AVL tree
how can this root be the median?
10
5 20
4 7 12
2 8
【在 g*******y 的大作中提到】
: 如果B堆个数比A堆多了2
: A.insert(B.extractTop());
|
g*******y
发帖数: 1930 | 34 my bad, I deleted my comments
【在 H*M 的大作中提到】
: This AVL tree
: how can this root be the median?
: 10
: 5 20
: 4 7 12
: 2 8
|
H*M
发帖数: 1268 | 35 I am still waiting for your solution of the o(n) of that histogram one...or
any hint like which direction to go? |
a*******g
发帖数: 12 | 36 you could probably use the same idea from the max rectangular matrix
use a stack to remember the open and close of rectangles
I don't know is this same as geniusxy's idea
or
【在 H*M 的大作中提到】
: I am still waiting for your solution of the o(n) of that histogram one...or
: any hint like which direction to go?
|
c******o
发帖数: 1277 | 37 easy one, use 2 heaps, one min, one max, and make sure they are the upper
half and lower half
keep updating them and if not balanced, just pop and reinsert.
very fast. |
E*******0
发帖数: 465 | |
