歌名进化史zz - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

歌名进化史zz

歌名进化史zz# Joke - 肚皮舞运动

b*n2009-12-07 08:12

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.

h*62009-12-07 08:12

2 楼

【以下文字转载自 EmergingNetworking 讨论区】
发信人: hunter2006 (王老汉(卖豆腐的)), 信区: EmergingNetworking
标题: 大家现在怎么传文件?
发信站: BBS 未名空间站 (Sat Aug 25 10:49:37 2012, 美东)
孩子同学的家长要毕业典礼的视频和照片,有好几G,不想跑来跑去用闪存之类的,email
又太大.以前都是用网盘,现在都禁了. 你们用什么?

c*g2009-12-07 08:12

3 楼

http://www.youtube.com/watch?v=QCbbuOfHoUk
附赠他的八个八度音域展示视频
http://www.youtube.com/watch?v=5KUhGQuOr3o

d*e2009-12-07 08:12

4 楼

【以下文字转载自 Music 讨论区】
发信人: dde (DDT), 信区: Music
标题: 歌名进化史zz
发信站: BBS 未名空间站 (Mon Dec 7 14:44:53 2009, 美东)
董文华《春天的故事》，杨千桦《夏天的故事》，陈艾玲《秋天的故事》，马天宇《
冬天的故事》。
王心凌《honey》，孙燕姿《honeyhoney》，萧亚轩《honeyhoneyhoney》
姜育恒《爱我你怕了吗》，孙燕姿《害怕》，王力宏《不要害怕》，潘玮柏《我不怕》
，赵薇《不怕》，郭美美《不怕不怕啦》，郑伊健《怕什么，什么也不怕》。
成龙《我是谁》，蟑螂《忘了我是谁》，蔡依林《你是谁》，许志安《忘了你是谁》。
萧亚轩《一辈子做你的女孩》，龙梅子《下辈子做你的女人》。
朴树《我爱你再见》，丁薇《再见我爱你》
苏永康《男人不该让女人流泪》，陈小春《女人不该让男人太累》
王心凌《爱你》，S.H.E《我爱你》，Beyond《真的爱你》，李宗盛《我是真的爱你》
，言承旭《我是真的真的很爱你》。
王菲《如果你是假的》，邓丽君《假如我是真的》，萧正楠《假如我是假的》，孟庭苇
《真的

g*y2009-12-07 08:12

5 楼

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*e2009-12-07 08:12

6 楼

dropbox?

d*e2009-12-07 08:12

7 楼

H*M2009-12-07 08:12

8 楼

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.

S*Y2009-12-07 08:12

9 楼

ftp

email

【在 h********6 的大作中提到】

: 【以下文字转载自 EmergingNetworking 讨论区】
: 发信人: hunter2006 (王老汉(卖豆腐的)), 信区: EmergingNetworking
: 标题: 大家现在怎么传文件?
: 发信站: BBS 未名空间站 (Sat Aug 25 10:49:37 2012, 美东)
: 孩子同学的家长要毕业典礼的视频和照片,有好几G,不想跑来跑去用闪存之类的,email
: 又太大.以前都是用网盘,现在都禁了. 你们用什么?

B*m2009-12-07 08:12

10 楼

居然发现这里面有个郭美美，是一个人么？

【在 d*e 的大作中提到】

: 【以下文字转载自 Music 讨论区】
: 发信人: dde (DDT), 信区: Music
: 标题: 歌名进化史zz
: 发信站: BBS 未名空间站 (Mon Dec 7 14:44:53 2009, 美东)
: 董文华《春天的故事》，杨千桦《夏天的故事》，陈艾玲《秋天的故事》，马天宇《
: 冬天的故事》。
: 王心凌《honey》，孙燕姿《honeyhoney》，萧亚轩《honeyhoneyhoney》
: 姜育恒《爱我你怕了吗》，孙燕姿《害怕》，王力宏《不要害怕》，潘玮柏《我不怕》
: ，赵薇《不怕》，郭美美《不怕不怕啦》，郑伊健《怕什么，什么也不怕》。
: 成龙《我是谁》，蟑螂《忘了我是谁》，蔡依林《你是谁》，许志安《忘了你是谁》。

H*M2009-12-07 08:12

11 楼

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
:

v*s2009-12-07 08:12

12 楼

不是，这个好像是新加坡歌手，除了这首以外，我从来没听过其他任何一首歌。

【在 B******m 的大作中提到】

: 居然发现这里面有个郭美美，是一个人么？

b*n2009-12-07 08:12

13 楼

有人说“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 的大作中提到】

R*a2009-12-07 08:12

14 楼

这么老的帖子都会啊。
其实这也不能叫进化史，因为不是按照出品时间排序的

【在 B******m 的大作中提到】

: 居然发现这里面有个郭美美，是一个人么？

g*y2009-12-07 08:12

15 楼

如果你的树中保持前驱后继指针
你每插一个数，Median要么不变，要么变成前驱，要么变成后继

【在 H*M 的大作中提到】

: how can u getmedian by o(1)??
:
: tree node, like prev, next pointers\

B*m2009-12-07 08:12

16 楼

这部search郭美美突然发现的么。

【在 R***a 的大作中提到】

: 这么老的帖子都会啊。
: 其实这也不能叫进化史，因为不是按照出品时间排序的

g*y2009-12-07 08:12

17 楼

实质就是一个list和tree的混合啦

【在 g*******y 的大作中提到】

: 如果你的树中保持前驱后继指针
: 你每插一个数，Median要么不变，要么变成前驱，要么变成后继

Q*T2009-12-07 08:12

18 楼

这个确实太old了
此郭美美貌似是新加坡歌手

【在 B******m 的大作中提到】

: 这部search郭美美突然发现的么。

b*n2009-12-07 08:12

19 楼

Predecessor和Successor都需要O(log(n))时间来找吧
他们都是随时可能变化的

【在 g*******y 的大作中提到】

: 如果你的树中保持前驱后继指针
: 你每插一个数，Median要么不变，要么变成前驱，要么变成后继

g*y2009-12-07 08:12

20 楼

你是说插入一个数之后，maintain 前驱后继的操作？我觉得是O(1)呢
你想，找插入位置，是利用树的性质，然后找到插入位置后，插入后maintain前驱后继的操作实质是一个双向链表的插入

【在 H*M 的大作中提到】

: how can u getmedian by o(1)??
:
: tree node, like prev, next pointers\

g*y2009-12-07 08:12

21 楼

这个带前驱后继的BST，实际上也是一个双向链表

【在 b*********n 的大作中提到】

: Predecessor和Successor都需要O(log(n))时间来找吧
: 他们都是随时可能变化的

H*M2009-12-07 08:12

22 楼

我说的不是这个
我意思是你每insert一个新数，首先需要update各个元素的前驱后继吧。否则前驱后继
这些信息就错了。
要不你详细写下。可能我理解错了你意思。

【在 g*******y 的大作中提到】

: 你是说插入一个数之后，maintain 前驱后继的操作？我觉得是O(1)呢
: 你想，找插入位置，是利用树的性质，然后找到插入位置后，插入后maintain前驱后继的操作实质是一个双向链表的插入

g*y2009-12-07 08:12

23 楼

你这样想啊，带前驱后继(按中序)的BST就是一个sorted的双向链表，你找到插入位置
后，在双向链表里插入一个元素，要多少时间？
不需要update每个数的前驱后继，只需要update O(1)个节点的前驱后继。 get it？
这个data structure好处就是把树跟链表结合在一起了，结合各自的优点

【在 H*M 的大作中提到】

: 我说的不是这个
: 我意思是你每insert一个新数，首先需要update各个元素的前驱后继吧。否则前驱后继
: 这些信息就错了。
: 要不你详细写下。可能我理解错了你意思。

H*M2009-12-07 08:12

24 楼

understood
挺高明！

【在 g*******y 的大作中提到】

: 你这样想啊，带前驱后继(按中序)的BST就是一个sorted的双向链表，你找到插入位置
: 后，在双向链表里插入一个元素，要多少时间？
: 不需要update每个数的前驱后继，只需要update O(1)个节点的前驱后继。 get it？
: 这个data structure好处就是把树跟链表结合在一起了，结合各自的优点

H*M2009-12-07 08:12

25 楼

其实我很想知道STL里面的ordered_map,是怎么实现的
应该是red_black tree,但是iterator++的话，输出successor(貌似O（1）),我怀疑是不是也加了这
种类似双向链表的东西。。

【在 H*M 的大作中提到】

: understood
: 挺高明！

g*y2009-12-07 08:12

26 楼

嗯，这个方法其实很不错的，感觉比树+链表略好一些，空间的常数因子都更小
一点，时间上我不是很确定，但是猜测这个方法应该也能略好一些，因为不需要向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*n2009-12-07 08:12

27 楼

can u detail how to maintain their sizes differ only by 1?

RBT一样必须搜索到底部然后再旋转若干次来保持平衡。堆的一个优点就是本身就是平
衡的了。的而且堆实现起来也比RBT容易很多很多。
a

【在 g*******y 的大作中提到】

: 嗯，这个方法其实很不错的，感觉比树+链表略好一些，空间的常数因子都更小
: 一点，时间上我不是很确定，但是猜测这个方法应该也能略好一些，因为不需要向RBT一样必须搜索到底部然后再旋转若干次来保持平衡。堆的一个优点就是本身就是平衡的了。的而且堆实现起来也比RBT容易很多很多。
: 关键就是在于保持小根堆和大根堆的size相差最多为1，
: 当某个堆的个数比另外一个堆多2个时，就需要移动一个到另外一个堆
: 而median始终是其中一个堆，或者两个堆的堆顶。

g*y2009-12-07 08:12

28 楼

如果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*e2009-12-07 08:12

29 楼

嗯是空间换时间。增加2n个指针，将search time从lgn提高到常数

【在 g*******y 的大作中提到】

k*k2009-12-07 08:12

30 楼

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*f2009-12-07 08:12

31 楼

找任意集合的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*e2009-12-07 08:12

32 楼

AVL tree, rotate after each insert, and the root is always the median.

insert(int
this

【在 b*********n 的大作中提到】

H*M2009-12-07 08:12

33 楼

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*b2009-12-07 08:12

34 楼

搞这么复杂，一个排序的数组不也可以：
o(logn) for insert
o(1) for median

h*r2009-12-07 08:12

35 楼

how to do inserting in log(N) in your case.

【在 l*********b 的大作中提到】

: 搞这么复杂，一个排序的数组不也可以：
: o(logn) for insert
: o(1) for median

b*n2009-12-07 08:12

36 楼

what's the algorithm for your white-board getMedian() function?
Anything special?
heap or selection algo?
Thank you

【在 k*k 的大作中提到】

t*l2009-12-07 08:12

37 楼

算法作业题。。。
3m heap...

c*n2009-12-07 08:12

38 楼

不能说具体点么

【在 t*********l 的大作中提到】

: 算法作业题。。。
: 3m heap...

o*r2009-12-07 08:12

39 楼

max+min是说把一半较小的元素放在max heap,另一半较大的放在min heap里么？

【在 k*k 的大作中提到】

h*e2009-12-07 08:12

40 楼

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*M2009-12-07 08:12

41 楼

?
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*e2009-12-07 08:12

42 楼

我想说“高度差不超过1”。

H*M2009-12-07 08:12

43 楼

u agree with blaze: using AVL tree can get the median by O(1)?

【在 g*******y 的大作中提到】

: 如果B堆个数比A堆多了2
: A.insert(B.extractTop());

H*M2009-12-07 08:12

44 楼

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*y2009-12-07 08:12

45 楼

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*M2009-12-07 08:12

46 楼

I am still waiting for your solution of the o(n) of that histogram one...or
any hint like which direction to go?

a*g2009-12-07 08:12

47 楼

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*o2009-12-07 08:12

48 楼

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*02009-12-07 08:12

49 楼

priority queue