新鲜的G家面筋

ryancooper 发表于 2016-4-5 10:52
最简单粗暴的做法就是可以这么来设计，底层storage可以用doubly linked list（remove的时候可以O(1)），存 ...

你好，我想问下remove的时候，map中的pair是不是也要删除呢，这样不还是log(n)？谢谢

jy_121 发表于 2016-4-26 07:17
你好，我想问下remove的时候，map中的pair是不是也要删除呢，这样不还是log(n)？谢谢

map的作用就是index，所以你底层存储变化的话，你的索引肯定要变。然后因为是treemap，所以是log的时间复杂度

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

kinggarden2001 发表于 2016-3-16 06:15
我觉得用Hashmap + sorted list 可以，如果要recent也要快的话再存一份数据到queue里。

用BST也可以， ...

请问 sorted list 是不是新加一个数时需要O（n）维持sorted attribute

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

一个map+三个堆， map<time, {minValueHeapNode, maxValueHeapNode, maxTimeHeapNode}>, 每个node都是一个pair(time, value)

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

Treemap+treeSet

1. class System{
   
2.         TreeMap<Integer,Integer> time_map = new TreeMap();
   
3.         TreeMap<Integer,HashSet<Integer>> value_map = new TreeMap();
   
4.         int getMax(){
   
5.                 if(value_map.size() == 0)
   
6.                         throw new Exception();
   
7.                 return value_map.lastKey();
   
8.         }
   
9.         int getMin(){
   
10.                 if(value_map.size() == 0)
    
11.                         throw new Exception();
    
12.                 return value_map.firstKey();
    
13.         }
    
14.         int getRecent(){
    
15.                 if(time_map.size() == 0)
    
16.                         throw new Exception();
    
17.                 return value_map.lastKey();
    
18.         }
    
19. 
    
20.         void add(long time, int price){
    
21.                 time_map.put(time,price);
    
22.                 if(!value_map.containsKey(price))
    
23.                         value_map.put(price,new HashSet());
    
24.                 value_map.get(price).put(time);
    
25.         }
    
26.         void update(long time, int price){
    
27.                 remove(time); // remove old value
    
28.                 add(time,price); // add new value
    
29.         }
    
30.         void remove(long time){
    
31.                 if(!time_map.containsKey(time))
    
32.                         throw new Exception();
    
33.                 int value = time_map.get(time);
    
34.                 time_map.remove(time);
    
35.                 value_map.get(value).remove(time);
    
36.                 if(value_map.get(value).size() == 0)// remove the set if empty
    
37.                         value_map.remove(value);
    
38.         }
    
39. }

复制代码