问题

面试题40. 最小的k个数
难度简单92收藏分享切换为英文关注反馈
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：
输入： arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

  • 0 <= k <= arr.length <= 10000
  • 0 <= arr[i] <= 10000

解答一

利用最小堆，使用 Java 的 util 包中的 priorityQueue ，将数组全部元素添加到 priorityQueue 中，然后依次取出 k 个元素，这些元素就是前 k 个 最小的元素
示例代码：

  1. class Solution {
  2.     public int[] getLeastNumbers(int[] arr, int k) {
  4.         PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(arr.length);
  5.         int[] smallest = new int[k];
  6.         for(int i = 0; i < arr.length; i ++)
  7.             priorityQueue.add(arr[i]);
  9.         for(int i = 0; i < k; i ++)
  10.             smallest[i] = priorityQueue.poll();
  12.         return smallest;
  13.     }
  14. }

执行结果：
执行用时 :28 ms, 在所有 Java 提交中击败了20.59 的用户。
内存消耗 :41.3 MB, 在所有 Java 提交中击败了100.00%的用户。

解答二

利用快速排序的思想，切分数组，依次比较切割点是否等于 k， 如果等于 k，那么左区间就是前 k 个元素。如果不等于，那么就继续进行切割

  1. class Solution {
  2.    public int[] getLeastNumbers(int[] arr, int k){
  3.          if(arr.length == 0 || k == 0)    return new int[0];
  4.          int v = 0;
  5.          int lo = 0, hi = arr.length -1;
  6.          while(true){ 
  7.             v = partition(arr, lo, hi);
  8.             if(v+1 < k)
  9.                 lo = v + 1;
  10.             else if(v+1 > k)
  11.                 hi = v - 1;
  12.             else   
  13.                 break;
  14.          }
  15.          int[]res = new int[k];
  16.          for(int i = 0; i < k; i ++)
  17.             res[i] = arr[i];
  18.          return res;
  19.     }
  20.     private int partition(int[] arr, int lo, int hi){
  21.         int v = arr[lo];
  22.         int i = lo+1, j = hi;
  23.         while(i <= j){
  24.             if(arr[i] > v)
  25.                 swap(arr, i, j--);
  26.             else
  27.                 i ++;
  28.         }
  29.         swap(arr, j, lo);
  30.         return j;
  31.     }
  32.     private void swap(int[] arr, int i , int j){
  33.         int temp = arr[i];
  34.         arr[i] = arr[j];
  35.         arr[j] = temp;
  36.     }
  37. }

执行结果：
执行用时 :3 ms, 在所有 Java 提交中击败了84.05% 的用户
内存消耗 :41 MB, 在所有 Java 提交中击败了100.00% 的用户