Top k Largest Numbers II

11/15/2017 更新
保持top k不需要判断新来的数和heap.peek()的大小。新add数先无脑加进heap,然后判断heap.size() > k ? poll() : return;

 public void add(int num) {  
     // write your code here  
     minHeap.add(num);  
     if(minHeap.size() > count) {  
       minHeap.poll();  
     }  
   }  
-----------------------------------------------------------------------------------------
思路:
用minheap在维持前k大的数,如果加进来的大于heap顶端那么replace。

实现:
Priorityqueue的iterator要留意一下。 Iterator it = minHeap.iterator();
这道题主要用到iterator的hasNext(), next方法。
还有就是Collections.sort(Collection, direction)。

代码如下:

 public class Solution {  
   /*  
   * @param k: An integer  
   */  
      private Queue<Integer> minHeap = new PriorityQueue<>();  
      private int count = 0;  
      public Solution(int k) {  
     // do intialization if necessary  
           count = k;  
   }  
   /*  
    * @param num: Number to be added  
    * @return: nothing  
    */  
   public void add(int num) {  
     // write your code here  
     if(minHeap.size() < count) {  
       minHeap.add(num);  
       return;  
     }   
     if(num > minHeap.peek())  
     {  
       minHeap.poll();  
       minHeap.add(num);  
     }  
   }  
   /*  
    * @return: Top k element  
    */  
   public List<Integer> topk() {  
     // write your code here  
           List<Integer> res = new ArrayList<>();  
        Iterator it = minHeap.iterator();  
           while(it.hasNext()) {  
             res.add((Integer)it.next());  
           }  
           Collections.sort(res, Collections.reverseOrder());  
           return res;  
   }  
 }  

评论

此博客中的热门博文

776. Split BST

663. Equal Tree Partition

532. K-diff Pairs in an Array