题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
分析：
找出最小的K个数字，可以通过维护一个大根堆来实现最小的K个数字，当大根堆的个数大于K的时候，把堆顶元素去掉，从而保证大根堆的大小为k。
同样，也可以通过使用冒泡排序算法，每次排序得到最小的数字的一个位置。这样就可以实现不用全部排序也可以得到最小的四个数字。
又是一道简单题，就不进行详细的分解了。
解答：
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> leastk = new ArrayList<Integer>();
if(input==null || input.length==0 || input.length<k) return leastk;
for(int i =0;i<k;i++) {
//冒泡排序，每次排序过程确定一个最小值
for(int j = input.length-1;j>i;j--){
if (input[j - 1] > input[j]) { //交换，把小的顶到前面去
int temp = input[j];
input[j] = input[j - 1];
input[j - 1]= temp;
}
}
leastk.add(input[i]);
}
return leastk;
}
}
运行结果
