今天是我坚持写题解的第 30 天！

题目描述（Medium）

设计一个算法，找出数组中最小的 k 个数。以任意顺序返回这 k 个数均可。

示例：

输入：arr = [1,3,5,7,2,4,6,8], k = 4

输出：[1,2,3,4]

提示：

0 <= len(arr) <= 100000
0 <= k <= min(100000, len(arr))

链接：https://leetcode-cn.com/problems/smallest-k-lcci

方法一、排序

这道题最简单的方法，排个序返回前 k 个元素即可。

代码如下：

classSolution{
publicint[]smallestK(int[]arr,intk){
Arrays.sort(arr);
int[]ans=newint[k];
System.arraycopy(arr,0,ans,0,k);
returnans;
}
}

• 时间复杂度：

  方法二、大顶堆

  我们可以使用大顶堆维护最小的 k 个元素，顶堆是这 k 个元素的最大值，每次来一个新的元素，如果它比堆顶元素小，说明它可以替换掉堆顶元素成为最小的 k 个元素，即把堆顶元素弹出并把这个元素入堆。

  使用大顶堆的好处是，我们可以很方便的查询到最小的这 k 个元素中的最大值，每次使用这个最大值与新元素比较即可。

  代码如下：

  classSolution{
  publicint[]smallestK(int[]arr,intk){
  int[]ans=newint[k];
  
  if(arr.length==0||k==0){
  returnans;
  }
  
  //大顶堆
  PriorityQueue<Integer>heap=newPriorityQueue<>((a,b)->b-a);
  for(intnum:arr){
  //堆元素数量不满k，直接入堆
  if(heap.size()<k){
  heap.offer(num);
  }elseif(num<heap.peek()){
  //新元素比堆顶元素小，弹出堆顶并让新元素入堆
  heap.poll();
  heap.offer(num);
  }
  }
  
  //遍历完所有元素，堆中的元素即为最小的k个元素
  for(inti=0;i<k;i++){
  ans[i]=heap.poll();
  }
  
  returnans;
  }
  }
  

  • 时间复杂度：

    方法三、基于快排的思想

    仔细分析这道题目，只是要求我们返回最小的 k 个元素，但是，并不需要把它们排好序，所以，我们可以使用快排的思想来操作。

    比如，给定 arr=[1,3,5,7,2,4,6,8], k=4，我们只要找到一个 轴 使得它左边的元素正好等于 k 个，那么，左边的元素都是比这个 轴 小的，也就是符合最小的 k 个元素的。

    比如，我们在某一次递归时，找到的轴正好是 5，那么数组可能变成了 [1,3,2,4,5,7,6,8]，这时，左边的元素数量正好等于 4 个，所以，这时候直接返回就可以了。

    

    另外，考虑 k=5 的时候，如果上面找到的轴也是 5，也是可以返回的，因为 5 及其左边的所有元素都比 5 右边的元素小，这一块请仔细体会下。

    请看代码：

    classSolution{
    publicint[]smallestK(int[]arr,intk){
    int[]ans=newint[k];
    
    if(arr.length==0||k==0){
    returnans;
    }
    
    quickSort(arr,0,arr.length-1,k);
    
    System.arraycopy(arr,0,ans,0,k);
    
    returnans;
    }
    
    privatevoidquickSort(int[]arr,intleft,intright,intk){
    if(left>=right){
    return;
    }
    //为了防止快排退化成O(n^2)使用随机位置的元素为轴
    intrand=ThreadLocalRandom.current().nextInt(right-left+1)+left;
    swap(arr,left,rand);
    intpivot=arr[left];
    inti=left,j=right;
    while(i<j){
    while(i<j&&arr[j]>pivot){
    j--;
    }
    while(i<j&&arr[i]<pivot){
    i++;
    }
    
    if(arr[i]==arr[j]&&i<j){
    i++;
    }else{
    swap(arr,i,j);
    }
    }
    
    //上面循环结束后i和j是相等的，即轴的新位置
    //如果轴的位置等于k或者k-1，直接返回
    if(i==k-1||i==k){
    return;
    }
    //如果轴的位置比k大，则需要对左边的元素重新操作，否则对右边的元素重新操作
    if(i>k){
    quickSort(arr,left,i-1,k);
    }else{
    quickSort(arr,i+1,right,k);
    }
    }
    
    privatevoidswap(int[]arr,inti,intj){
    inttmp=arr[i];
    arr[i]=arr[j];
    arr[j]=tmp;
    }
    }
    

    • 时间复杂度：介于

      最后

      如果对你有帮助，请点个赞吧，谢谢^^

      也可以我的公号【彤哥来刷题啦】，每日分享题解，一起刷题，一起拿全家桶。