本文共 1660 字，大约阅读时间需要 5 分钟。

题目描述

给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。如果K>数组的长度，那么返回一个空的数组输入[4,5,1,6,2,7,3,8],4 返回值[1,2,3,4]

题目分析

1. 我们知道一趟冒泡排序可以使一个元素在其正确的位置上，因此我们可以进行k趟排序，每趟排序排序使一个无序序列中最小的放在其正确的位置上，那么排完序之后前k-1个数即是最小的数字。但是其时间复杂度为o(n²)>
2. 借助排序算法对数组进行排序，然后取前（k-1）个元素。时间复杂度最小为o(nlogn)。
3. 使用小根堆排序，我们知道小根堆的最小值一定在根节点处，因此我们知道循环输出k次根节点就可以得到前k个最小值，时间复杂度为o(nlogn)，下面给出代码：

import java.util.ArrayList;public class Solution {       ArrayList
   
     res = new ArrayList();    public ArrayList
    
      GetLeastNumbers_Solution(int [] input, int k) {          if(input.length < k || k == 0 ) {              return res;       }        //构建小根堆        for(int i = input.length / 2 - 1; i >= 0; i--) {               adjustSmallTree(input,input.length-1,i);        }        //输出最小的四个数        for(int j = input.length-1;j >=0;j--) {               res.add(input[0]);            k--;            if(k == 0) {                   break;            }            input[0] = input[j];            adjustSmallTree(input,j-1,0);        }        return res;    }    //调整以root为根节点的数为小根堆    public void adjustSmallTree(int[] input,int len,int root) {           //数组长度小于等于0，直接返回        if(len <= 0) {               return;        }        for(int i = 2 * root + 1; i <= len; i = i * 2 + 1) {               //如果root有左右子树，并且右子树值小于左子树值，i指向右子树            if(i + 1 <= len && input[i] > input[i+1]) {                   i++;            }            //如果左右节点最大值小于根节点值            if(input[i] < input[root]) {                   int temp = input[i];                input[i] = input[root];                input[root] = temp;            } else {   //如果子树最小值大于根节点值                break;            }        }    }    }