題目描述
輸入n個整數(shù)庐椒，找出其中最小的K個數(shù)氧映。例如輸入4,5,1,6,2,7,3,8這8個數(shù)字类垦，則最小的4個數(shù)字是1,2,3,4,。
分析：
找出最小的K個數(shù)字以故，可以通過維護一個大根堆來實現(xiàn)最小的K個數(shù)字蜗细，當大根堆的個數(shù)大于K的時候，把堆頂元素去掉怒详，從而保證大根堆的大小為k炉媒。
同樣，也可以通過使用冒泡排序算法昆烁，每次排序得到最小的數(shù)字的一個位置吊骤。這樣就可以實現(xiàn)不用全部排序也可以得到最小的四個數(shù)字。
又是一道簡單題静尼，就不進行詳細的分解了白粉。
解答：
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]) { //交換鼠渺，把小的頂?shù)角懊嫒? int temp = input[j];
input[j] = input[j - 1];
input[j - 1]= temp;
}
}
leastk.add(input[i]);
}
return leastk;
}
}
運行結(jié)果
