一、问题

在一个很长的数组中，求出top k大小的数目

 

二、办法

• 用优先队列
• 时间复杂度O(nlog(k))，应该是最差的情况下是这个

三、Code

1 package algorithm; 2  3 import java.util.ArrayList; 4 import java.util.Comparator; 5 import java.util.List; 6 import java.util.PriorityQueue; 7  8 /** 9  * Created by adrian.wu on 2019/2/18.10  */11 public class TopKNums {12     public List
     
       topKnums(int[] nums, int k) {13         PriorityQueue
      
        pq = new PriorityQueue<>(new Comparator
       
        () {14             @Override15             public int compare(Integer o1, Integer o2) {16                 return o2.compareTo(o1);17             }18         });19         for (int i = 0; i < k; i++)20             pq.add(nums[i]);21 22         for (int i = k; i < nums.length; i++) {23             if (pq.peek() != null && pq.peek() > nums[i]) {24                 pq.poll();25                 pq.offer(nums[i]);26             }27         }28 29         List
        
          list = new ArrayList<>();30         while (pq.peek() != null) list.add(pq.poll());31         return list;32     }33 }