最近看到了 java.util.PriorityQueue。刚看到还没什么感觉，今天突然发现他可以用来找N个数中最小的K个数。
假设有如下 10 个整数。
5 2 0 1 4 8 6 9 7 3
怎么找出最小的 5 个数呢？很好想到的方法是先升序排序，然后取前 5 个就可以。
至于怎么排序方法有很多，比如简单的冒泡，选择，”难点”的有快速，希尔和堆等等。
先看看这种比较少见的实现方法的代码，再看看下面的简单介绍。
PriorityQueue实现
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
public class FindSmallestKofNNumbers {
public List<Integer> findSmallestKofNNumbers( int[] numbers,
int k) {
Queue<Integer> queue = new PriorityQueue<>();
for (int i : numbers) {
queue.add(i);
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < k; ++i) {
ans.add(queue.poll());// 取k个数加到列表中
}
return ans;
}
}
看完没，代码简单吧，核心代码就几句。创建一个 PriorityQueue 对象，调用 add 方法和 poll 方法。
- 创建一个
Integer类型的一个基于优先级堆的无界优先级队列。元素是按照队列元素的自然顺序进行排序。此队列的头是按指定方式确定的最小的元素，如果多个元素都是最小值，则头是其中一个元素——选择方法任意。 boolean add(E e)将 e 插入此优先级队列。E poll()获取并移除此队列的头，如果此队列为空，则返回null。
Arrays.sort()实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class FindSmallestKofNNumbers {
public List<Integer> findSmallestKofNNumbers( int[] numbers,
int k) {
int[] arr = Arrays.copyOf(numbers, numbers.length);
Arrays.sort(arr);
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < k; ++i) {
ans.add(arr[i]);// 取k个数加到列表中
}
return ans;
}
}