剑指 Offer 40. 最小的k个数

常规法

  1. public int[] getLeastNumbers(int[] arr, int k) {
  2.         int[] vec = new int[k];
  3.         Arrays.sort(arr);
  4.         for (int i = 0; i < k; ++i) {
  5.             vec[i] = arr[i];
  6.         }
  7.         return vec;
  8.     }
  10. 作者：LeetCode-Solution
  11. 链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/zui-xiao-de-kge-shu-by-leetcode-solution/

堆

  1. class Solution {
  2.     public int[] getLeastNumbers(int[] arr, int k) {
  3.         int[] vec = new int[k];
  4.         if (k == 0) { // 排除 0 的情况
  5.             return vec;
  6.         }
  7.         PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
  8.             public int compare(Integer num1, Integer num2) {
  9.                 return num2 - num1;
  10.             }
  11.         });
  12.         for (int i = 0; i < k; ++i) {
  13.             queue.offer(arr[i]);
  14.         }
  15.         for (int i = k; i < arr.length; ++i) {
  16.             if (queue.peek() > arr[i]) {
  17.                 queue.poll();
  18.                 queue.offer(arr[i]);
  19.             }
  20.         }
  21.         for (int i = 0; i < k; ++i) {
  22.             vec[i] = queue.poll();
  23.         }
  24.         return vec;
  25.     }
  26. }
  28. 作者：LeetCode-Solution
  29. 链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/zui-xiao-de-kge-shu-by-leetcode-solution/
  1. class Solution {
  2.     public int[] getLeastNumbers(int[] arr, int k) {
  4.         if (k == 0) {
  5.             return new int[0];
  6.         }
  7.         // 使用一个最大堆（大顶堆）
  8.         // Java 的 PriorityQueue 默认是小顶堆，添加 comparator 参数使其变成最大堆
  9.         Queue<Integer> heap = new PriorityQueue<>(k, (i1, i2) -> Integer.compare(i2, i1));
  11.         for (int e : arr) {
  12.             // 当前数字小于堆顶元素才会入堆
  13.             if (heap.isEmpty() || heap.size() < k || e < heap.peek()) {
  14.                 heap.offer(e);
  15.             }
  16.             if (heap.size() > k) {
  17.                 heap.poll(); // 删除堆顶最大元素
  18.             }
  19.         }
  21.         // 将堆中的元素存入数组
  22.         int[] res = new int[heap.size()];
  23.         int j = 0;
  24.         for (int e : heap) {
  25.             res[j++] = e;
  26.         }
  27.         return res;
  28.     }
  30. // 作者：nettee
  31. // 链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/tu-jie-top-k-wen-ti-de-liang-chong-jie-fa-you-lie-/
  33. }

Arrays.sort()

时间复杂度 n_log_n
_
堆，时间复杂度 O(nlog⁡k)。