用什么数据结构快速insert, get median - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

用什么数据结构快速insert, get median

用什么数据结构快速insert, get median# JobHunting - 待字闺中

h*52011-08-24 07:08

1 楼

请问各位老师当年和现在都是如何拒绝offer的？是打电话还是发电邮？跟HR联系还是
招人的老板?
给的理由呢？家庭原因，比如配偶不同意？在精华区翻了一遍，没找到。版内搜索也没
有,在标题里搜索reject, decline或据，都没有。希望大家分享一下自己或知道的经历
。谢谢！

s*d2011-08-24 07:08

2 楼

我想着用balanced binary search tree: insert:O(logn), get median:O(logn)
或者linked list: 指针指中间, insert: O(1), get median: O(1)
不过感觉好像有问题

i*u2011-08-24 07:08

3 楼

拒绝offer不用太做作了，简单发个email，说是personnel reason can not take the
offer就完了

P*c2011-08-24 07:08

4 楼

经典题。一个min heap. 一个max heap. 保证大致一样大。

h*52011-08-24 07:08

5 楼

谢谢。

the

【在 i******u 的大作中提到】

: 拒绝offer不用太做作了，简单发个email，说是personnel reason can not take the
: offer就完了

f*t2011-08-24 07:08

6 楼

linked list的insert不可能是O(1)吧……应该是O(n)

m*e2011-08-24 07:08

7 楼

电话。不想burn the bridge

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

: 请问各位老师当年和现在都是如何拒绝offer的？是打电话还是发电邮？跟HR联系还是
: 招人的老板?
: 给的理由呢？家庭原因，比如配偶不同意？在精华区翻了一遍，没找到。版内搜索也没
: 有,在标题里搜索reject, decline或据，都没有。希望大家分享一下自己或知道的经历
: 。谢谢！

G*n2011-08-24 07:08

8 楼

单纯的insert是o(1)
但是如果要考虑上搜索位置是O(n)咯

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

: linked list的insert不可能是O(1)吧……应该是O(n)

b*82011-08-24 07:08

9 楼

这是标准答案。如果用fibonacci堆，可以达到时空都是O(1)，平摊分析下。

【在 P**********c 的大作中提到】

: 经典题。一个min heap. 一个max heap. 保证大致一样大。

w*s2011-08-24 07:08

10 楼

能不能展开讲一下min heap. 一个max heap怎么找中值?

j*w2011-08-24 07:08

11 楼

Insert all input data into max_heap and min_heap. O(n)+O(n) = O(n)
x = max_heap.top();
y = min_heap.top();
while (x != y)
{
max_heap.pop();
min_heap.pop();
x = max_heap.top();
y = min_heap.top();
}
ret = x;
// while loop is O(n/2 * log n)

P*c2011-08-24 07:08

12 楼

insert过程中，保证两个heap一样大，或者max heap多一。max heap里的所有值小于min heap里的所有值。每次insert只需要比较要insert的数跟两个heap的root决定进哪个heap, 如果insert后两个heap大小不满足要求则把其中一个的root插到另一个。 insert复杂度O(lgn).
找median时，如果两个heap一样大，则median为两个root的平均。
如果max heap多一，则为max heap的root
找median操作为O(1).

【在 w*******s 的大作中提到】

: 能不能展开讲一下min heap. 一个max heap怎么找中值?