面试必问：找出一组数中最小的K个数（海量数据Top K问题）

  • 2019 年 11 月 6 日
  • 筆記

题目

输入 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 LeastK {        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");          }            int start = 0;          int end = input.length - 1;          int index = partition(input, start, end); //切分后左子数组的长度          int target = output.length - 1; //K-1            //若切分后左子数组长度不等于K          while (index != target) {              //若切分后左子数组长度小于K，那么继续切分右子数组，否则继续切分左子数组              if (index < target) {                  start = index + 1;              } else {                  end = index - 1;              }              index = partition(input, start, end);          }            System.arraycopy(input, 0, output, 0, output.length);      }        private static int partition(int arr[], int left, int right) {          int i = left;          int j = right + 1;          int pivot = arr[left];            while (true) {              //找到左边大于pivot的数据，或者走到了最右边仍然没有找到比pivot大的数据              while (i < right && arr[++i] < pivot) { //求最大的k个数时，arr[++i] > pivot                  if (i == right) {                      break;                  }              }              //找到右边小于pivot的数据，或者走到了最左边仍然没有找到比pivot小的数据              while (j > left && arr[--j] > pivot) { //求最大的k个数时，arr[--j] < pivot                  if (j == left) {                      break;                  }              }              //左指针和右指针重叠或相遇，结束循环              if (i >= j) {                  break;              }              //交换左边大的和右边小的数据              swap(arr, i, j);          }          //此时的 a[j] <= pivot，交换之          swap(arr, left, j);          return j;      }        private static void swap(int[] arr, int i, int j) {          int tmp = arr[i];          arr[i] = arr[j];          arr[j] = tmp;      }    }

采用上面的思路是有限制的，比如需要修改输入的数组，因为函数 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]);      }    }

VirMach 便宜 VPS

QNews

QNews