Pocket Gems面经题求助

reboot329 发表于 2016-12-28 23:23
我是按每种东西的最大数量打包，不够的也打成一个包。PQ存包，comparator按照包里的总价值，然后就是k larg ...

没错,这样就可以简化成top k的缩减版了

xiuluoxn 发表于 2016-12-28 17:05
突然想到heap的优化了, 你的code复杂度是O(k*n), 相对于每个slot, worst case要遍历整个items(或余下的) ...

想请问下楼主，heap的做法为什么是nlog(k)呢？

遍历整个数组是n (item 个数), 遍历同时维护k size的heap是log(k). 所以我觉得是nlog(k).

1. public static int maxValue(int n, String[] stuff, item[] items ){
   
2.         Map<String, Integer> cntMap = new HashMap<String,Integer>();
   
3.         for(String s:stuff){
   
4.             cntMap.put(s,cntMap.getOrDefault(s,0)+1);
   
5.         }
   
6.         PriorityQueue<Integer> maxHeap =
   
7.                          new PriorityQueue<>((x,y)->(y-x));
   
8.         Map<String, item> itemMap = new HashMap<String, item>();
   
9.         for(item i: items){
   
10.             itemMap.put(i.name, i);
    
11.         }
    
12.         
    
13.         for(String key: cntMap.keySet()){
    
14.             int amt = cntMap.get(key);
    
15.             int maxStack = itemMap.get(key).max_stack;
    
16.             int value = itemMap.get(key).value;
    
17.             if(amt>maxStack){
    
18.                 maxHeap.add(value*maxStack);
    
19.                 maxHeap.add(value*(amt-maxStack));
    
20.             }else{
    
21.                 maxHeap.add(value*amt);
    
22.             }
    
23.             
    
24.         }
    
25.         int t=0, rlt = 0;
    
26.         while(t<n){
    
27.             rlt+=maxHeap.poll();
    
28.             t++;
    
29.         }
    
30.         return rlt;
    
31.         
    
32.     }

复制代码

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

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

CSIYI 发表于 2017-6-29 03:12

maxHeap.add(value*(amt-maxStack));
这一句是不是有问题啊 amt-maxStack有可能依然大于maxStack，那么就不可以放入堆中吧