一、问题
在一个很长的数组中,求出top k大小的数目
二、办法
- 用优先队列
- 时间复杂度O(nlog(k)),应该是最差的情况下是这个
三、Code
package algorithm; import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.PriorityQueue; /** * Created by adrian.wu on 2019/2/18. */ public class TopKNums { public List<Integer> topKnums(int[] nums, int k) { PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o2.compareTo(o1); } }); for (int i = 0; i < k; i++) pq.add(nums[i]); for (int i = k; i < nums.length; i++) { if (pq.peek() != null && pq.peek() > nums[i]) { pq.poll(); pq.offer(nums[i]); } } List<Integer> list = new ArrayList<>(); while (pq.peek() != null) list.add(pq.poll()); return list; } }