过年到香港扫货ZT (转载) - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

过年到香港扫货ZT (转载)

过年到香港扫货ZT (转载)# Joke - 肚皮舞运动

a*02015-02-15 08:02

1 楼

设计查询系统(最大值，最小值，最新加入值)
class System {
int getMax();
int getMin()
int getRecent()

void add(long time, int price)
void update(long time, int price)
void remove(long time);
}
例子如下
add(1,4) max:4, min:4, recent:4
add(4,7) max:7, min:4, recent:7
add(2,5) max:7, min:4, recent:7
etc..
这题维度太多，又有值又有时间，不知道最优的data structure是什么...

f*r2015-02-15 08:02

2 楼

【以下文字转载自 Military 讨论区】
发信人: gc01 (gc01), 信区: Military
标题: 过年到香港扫货ZT
发信站: BBS 未名空间站 (Sun Feb 15 13:04:35 2015, 美东)
示威者揮龍獅旗　圍觀者拍掌歡呼 (04:59)

r*y2015-02-15 08:02

3 楼

我只能设计出add update remove getmin getmax getrecent 全部是logN的data
structure。感觉应该有get全部是O(1)的solution

f*n2015-02-15 08:02

4 楼

为什么要捂脸? 丢脸的难道不是那些举牌子的?

s*72015-02-15 08:02

5 楼

TreeMap
TreeMap
all update operation should be log(N), and all get operation O(1)

d*f2015-02-15 08:02

6 楼

举牌子的已经不要脸了，所以不需要捂脸

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

: 为什么要捂脸? 丢脸的难道不是那些举牌子的?

b*62015-02-15 08:02

7 楼

这个结构怎么样，可以存两个信息，tree按时间排，heap按值排。这样可以实现add,
remove的logn，get max的O(1)，但是不能同时get min, 建两个treap可以解决问题不
过面试的时候应该不能用
https://en.wikipedia.org/wiki/Treap

b*e2015-02-15 08:02

8 楼

举牌子都戴口罩知道丢脸

★ 发自iPhone App: ChineseWeb 1.0.1

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

: 举牌子的已经不要脸了，所以不需要捂脸

r*y2015-02-15 08:02

9 楼

That's wrong

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

: TreeMap
: TreeMap
: all update operation should be log(N), and all get operation O(1)

n*d2015-02-15 08:02

10 楼

建议切断香港淡水供应，让爱英国港人从英国买

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

: 【以下文字转载自 Military 讨论区】
: 发信人: gc01 (gc01), 信区: Military
: 标题: 过年到香港扫货ZT
: 发信站: BBS 未名空间站 (Sun Feb 15 13:04:35 2015, 美东)
: 示威者揮龍獅旗　圍觀者拍掌歡呼 (04:59)

s*72015-02-15 08:02

11 楼

No, you are wrong.

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

: That's wrong

b*e2015-02-15 08:02

12 楼

这样不好涨价就成有生意还是应该做

★ 发自iPhone App: ChineseWeb 1.0.1

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

: 建议切断香港淡水供应，让爱英国港人从英国买

a*02015-02-15 08:02

13 楼

logN的是什么？
这种对顺序查询的O(1)不太可能吧

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

: 我只能设计出add update remove getmin getmax getrecent 全部是logN的data
: structure。感觉应该有get全部是O(1)的solution

n*d2015-02-15 08:02

14 楼

这样更会助长高收入港人的优越感

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

: 这样不好涨价就成有生意还是应该做
:
: ★ 发自iPhone App: ChineseWeb 1.0.1

c*22015-02-15 08:02

15 楼

如果更新和查询都是logN，那查询可以做到O1，用三个变量保留查询结果，每次更新的
时候也更新他们就是。
话说回来，如果只需要这三个查询的值，可以不用任何数据结构，保留最近时间和它对
应的值，保留最大最小值就好了……我是不是哪里想错了……

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

: 我只能设计出add update remove getmin getmax getrecent 全部是logN的data
: structure。感觉应该有get全部是O(1)的solution

c*t2015-02-15 08:02

16 楼

这些港灿的脑子都让门挤了。香港零制造业，不做大陆的生意，香港人都要喝西北风了
。

c*22015-02-15 08:02

17 楼

哦，remove只有时间，还是要一个tree

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

: 如果更新和查询都是logN，那查询可以做到O1，用三个变量保留查询结果，每次更新的
: 时候也更新他们就是。
: 话说回来，如果只需要这三个查询的值，可以不用任何数据结构，保留最近时间和它对
: 应的值，保留最大最小值就好了……我是不是哪里想错了……

q*n2015-02-15 08:02

18 楼

怎么搞的跟卖淫被抓似的。。。

w*z2015-02-15 08:02

19 楼

一个map 一个set
map的key是time, value是price
set存所有的price.
这样所有的Get都是O(1), 所有的Update都是O(logN)

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

: 设计查询系统(最大值，最小值，最新加入值)
: class System {
: int getMax();
: int getMin()
: int getRecent()
:
: void add(long time, int price)
: void update(long time, int price)
: void remove(long time);
: }