算法题解：最小的K个数（海量数据Top K问题）
题目
输入 n 个整数，找出其中最小的 k 个数。例如输入4、5、1、6、2、7、3、8 这8个数字，则最小的4个数字是1、2、3、4。
初窥
这道题最简单的思路莫过于把输入的 n 个整数排序，排序之后位于最前面的 k 个数就是最小的 k 个数。这种思路的时间复杂度是 O(nlogn)。
解法一：脱胎于快排的O(n)的算法
如果基于数组的第 k 个数字来调整，使得比第 k 个数字小的所有数字都位于数组的左边，比第 k 个数字大的所有数字都位于数组的右边。这样调整之后，位于数组中左边的 k 个数字就是最小的 k 个数字（这 k 个数字不一定是排序的）。下面是基于这种思路的参考代码：
public class QuickSortLeastK {
/**
* 最小的K个数
*/
public static int[] getLeastNumbers(int[] arr, int k) {
if (k == 0) {
return new int[0];
}
int left = 0;
int right = arr.length - 1;
int pivotIndex = partition(arr, left, right);
// 最小的 k 个数，从小到大排序后，索引为 k -1
int targetIndex = k - 1;
while (pivotIndex != targetIndex) {
if (pivotIndex > targetIndex) {
right = pivotIndex - 1;
} else {
left = pivotIndex + 1;
}
pivotIndex = partition(arr, left, right);
}
int[] out = new int[k];
System.arraycopy(arr, 0, out, 0, k);
return out;
}
/**
* 快排，返回基准值坐标
*/
private static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
int markPoint = left;
for (int i = left + 1; i <= right; i++) {
if (arr[i] < pivot) {
markPoint++;
swap(arr, i, markPoint);
}
}
swap(arr, left, markPoint);
return markPoint;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
采用上面的思路是有限制的，比如需要修改输入的数组，因为函数 Partition 会调整数组中的顺序，当然了，这个问题完全可以通过事先拷贝一份新数组来解决。值得说明的是，这种思路是不适合处理海量数据的。若是遇到海量数据求最小的 k 个数的问题，可以使用下面的解法。
解法二：适合处理海量数据的O(nlogk)的算法
我们可以先创建一个大小为K的数据容器来存储最小的 k 个数字，接下来我们每次从输入的 n 个整数中读入一个数。如果容器中已有的数字少于 k 个，则直接把这次读入的整数放入容器之中；如果容器中已有 k 个数字了，也就是容器已满，此时我们不能再插入新的数字而只能替换已有的数字。找出这已有的 k 个数中的最大值，然后拿这次待插入的整数和最大值进行比较。如果待插入的值比当前已有的最大值小，则用这个数替换当前已有的最大值；如果待插入的值比当前已有的最大值还要大，那么这个数不可能是最小的 k 个整数之一，于是我们可以抛弃这个整数。
因此当容器满了之后，我们要做 3 件 事情：一是在 k 个整数中找到最大数；二是有可能在这个容器中删除最大数；三是有可能要插入一个新的数字。如果用一个二叉树来实现这个数据容器，那么我们能在O(logk)时间内实现这三步操作。因此对于 n 个输入数字而言，总的时间效率就是O(nlogk)。
我们可以选择用不同的二叉树来实现这个数据容器。由于每次都需要找到 k 个整数中的最大数字，我们很容易想到用最大堆。在最大堆中，根结点的值总是大于它的子树中任意结点的值。于是我们每次可以在 O(1) 得到已有的 k 个数字中的最大值，但需要 O(logk) 时间完成删除及插入操作。
我们自己从头实现一个最大堆需要一定的代码，这在面试短短的几十分钟内很难完成。我们还可以采用 Java 提供的具有优先级的队列来实现我们的容器。
public class LeastK {
public static Integer[] getLeastNumbers(int[] nums, int k) {
// 默认自然排序，需手动转为降序
PriorityQueue<Integer> maxQueue = new PriorityQueue<>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
if (o1 > o2) {
return -1;
} else if (o1 < o2) {
return 1;
}
return 0;
}
});
for (int num : nums) {
if (maxQueue.size() < k || num < maxQueue.peek()) { // peek()：返回队列头部的值，也就是队列最大值
// 插入元素
maxQueue.offer(num);
}
if (maxQueue.size() > k) {
// 删除队列头部
maxQueue.poll();
}
}
return maxQueue.toArray(new Integer[0]);
}
}
海量数据Top K
Top K 问题是在面试中经常被问到的问题，比如：从20亿个数字的文本中，找出最大的前100个。
若是遇到此类求海量数据中最大的 k 个数的问题，可以参考上面的求最小的 k 个数，改用最小堆，实现如下的 Java 代码：
public class TopK {
public Integer[] getLargestNumbers(int[] nums, int k) {
PriorityQueue<Integer> minQueue = new PriorityQueue<>(k); // 默认自然排序
for (int num : nums) {
if (minQueue.size() < k || num > minQueue.peek()) { // peek()：返回队列头部的值，也就是队列最小值
// 插入元素
minQueue.offer(num);
}
if (minQueue.size() > k) {
// 删除队列头部
minQueue.poll();
}
}
return minQueue.toArray(new Integer[0]);
}
}
最大堆源码
如果对最大堆的实现源码比较感兴趣的话，可以参考下面的代码自行学习。
public class MaxHeapAndTopK {
/**
* 大顶堆
*
* @param <T> 参数化类型
*/
private final static class MaxHeap<T extends Comparable<T>> {
// 堆中元素存放的集合
private List<T> items;
// 用于计数
private int cursor;
/**
* 构造一个椎，始大小是32
*/
public MaxHeap() {
this(32);
}
/**
* 造诣一个指定初始大小的堆
*
* @param size 初始大小
*/
public MaxHeap(int size) {
items = new ArrayList<>(size);
cursor = -1;
}
/**
* 向上调整堆
*
* @param index 被上移元素的起始位置
*/
public void siftUp(int index) {
T intent = items.get(index); // 获取开始调整的元素对象
while (index > 0) { // 如果不是根元素
int parentIndex = (index - 1) / 2; // 找父元素对象的位置
T parent = items.get(parentIndex); // 获取父元素对象
if (intent.compareTo(parent) > 0) { //上移的条件，子节点比父节点大
items.set(index, parent); // 将父节点向下放
index = parentIndex; // 记录父节点下放的位置
} else { // 子节点不比父节点大，说明父子路径已经按从大到小排好顺序了，不需要调整了
break;
}
}
// index此时记录是的最后一个被下放的父节点的位置（也可能是自身），所以将最开始的调整的元素值放入index位置即可
items.set(index, intent);
}
/**
* 向下调整堆
*
* @param index 被下移的元素的起始位置
*/
public void siftDown(int index) {
T intent = items.get(index); // 获取开始调整的元素对象
int leftIndex = 2 * index + 1; // // 获取开始调整的元素对象的左子结点的元素位置
while (leftIndex < items.size()) { // 如果有左子结点
T maxChild = items.get(leftIndex); // 取左子结点的元素对象，并且假定其为两个子结点中最大的
int maxIndex = leftIndex; // 两个子节点中最大节点元素的位置，假定开始时为左子结点的位置
int rightIndex = leftIndex + 1; // 获取右子结点的位置
if (rightIndex < items.size()) { // 如果有右子结点
T rightChild = items.get(rightIndex); // 获取右子结点的元素对象
if (rightChild.compareTo(maxChild) > 0) { // 找出两个子节点中的最大子结点
maxChild = rightChild;
maxIndex = rightIndex;
}
}
// 如果最大子节点比父节点大，则需要向下调整
if (maxChild.compareTo(intent) > 0) {
items.set(index, maxChild); // 将子节点向上移
index = maxIndex; // 记录上移节点的位置
leftIndex = index * 2 + 1; // 找到上移节点的左子节点的位置
} else { // 最大子节点不比父节点大，说明父子路径已经按从大到小排好顺序了，不需要调整了
break;
}
}
// index此时记录是的最后一个被上移的子节点的位置（也可能是自身），所以将最开始的调整的元素值放入index位置即可
items.set(index, intent);
}
/**
* 向堆中添加一个元素
*
* @param item 等待添加的元素
*/
public void add(T item) {
items.add(item); // 将元素添加到最后
siftUp(items.size() - 1); // 循环上移，以完成重构
}
/**
* 删除堆顶元素
*
* @return 堆顶部的元素
*/
public T deleteTop() {
if (items.isEmpty()) { // 如果堆已经为空，就报出异常
throw new RuntimeException("The heap is empty.");
}
T maxItem = items.get(0); // 获取堆顶元素
T lastItem = items.remove(items.size() - 1); // 删除最后一个元素
if (items.isEmpty()) { // 删除元素后，如果堆为空的情况，说明删除的元素也是堆顶元素
return lastItem;
}
items.set(0, lastItem); // 将删除的元素放入堆顶
siftDown(0); // 自上向下调整堆
return maxItem; // 返回堆顶元素
}
/**
* 获取下一个元素
*
* @return 下一个元素对象
*/
public T next() {
if (cursor >= items.size()) {
throw new RuntimeException("No more element");
}
return items.get(cursor);
}
/**
* 判断堆中是否还有下一个元素
*
* @return true堆中还有下一个元素，false堆中无下五元素
*/
public boolean hasNext() {
cursor++;
return cursor < items.size();
}
/**
* 获取堆中的第一个元素
*
* @return 堆中的第一个元素
*/
public T first() {
if (items.size() == 0) {
throw new RuntimeException("The heap is empty.");
}
return items.get(0);
}
/**
* 判断堆是否为空
*
* @return true是，false否
*/
public boolean isEmpty() {
return items.isEmpty();
}
/**
* 获取堆的大小
*
* @return 堆的大小
*/
public int size() {
return items.size();
}
/**
* 清空堆
*/
public void clear() {
items.clear();
}
@Override
public String toString() {
return items.toString();
}
}
/**
* 题目： 输入n个整数，找出其中最小的k个数
*
* @param input 输入数组
* @param output 输出数组
*/
public static void getLeastNumbers(int[] input, int[] output) {
if (input == null || output == null || output.length <= 0 || input.length < output.length) {
throw new IllegalArgumentException("Invalid args");
}
MaxHeap<Integer> maxHeap = new MaxHeap<>(output.length);
for (int i : input) {
if (maxHeap.size() < output.length) {
maxHeap.add(i);
} else {
int max = maxHeap.first();
if (max > i) {
maxHeap.deleteTop();
maxHeap.add(i);
}
}
}
for (int i = 0; maxHeap.hasNext(); i++) {
output[i] = maxHeap.next();
}
}
}
参考资料
[1] 《剑指offer》
版权声明：凡未经本网站书面授权，任何媒体、网站及个人不得转载、复制、重制、改动、展示或使用本网站的局部或全部的内容或服务，或在非本网站所属服务器上建立镜像。如果已转载，请自行删除。同时，我们保留进一步追究相关行为主体的法律责任的权利。我们希望与各媒体合作，签订著作权有偿使用许可合同，故转载方须书面/邮件申请，以待商榷。
