最小的K个数（java）

题目描述

输入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;
    }
}

运行结果