输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。
package 练习;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
public class Solution {
static public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list = new ArrayList<>();
if(input==null || k>input.length || k==0)
return list;
//存放k个值,按从大到小排列
PriorityQueue<Integer> queue = new PriorityQueue<>(k, Collections.reverseOrder());
for (int i = 0; i < input.length; i++) {
//前k个直接存
if(i<k){
//PriorityQueue会自动排序
queue.offer(input[i]);
//存入list
list.add(input[i]);
//前k个之后的进行比较(与最大堆了堆顶元素比较)
}else{
//如果第i个元素 < 最大堆的顶元素 就把最大堆的顶元素取出,然后重新把这个小的值存入
if(queue.peek() > input[i]) {
//删除list中这个最大的元素
list.remove(queue.peek());
//把较上一个小的存入
list.add(input[i]);
//最大堆也更新
queue.poll();
queue.offer(input[i]);
}
}
}
//这样也行
// for (int i=0;i<k;i++){
// list.add(queue.poll());
// }
//返回List
return list;
}
public static void main(String[] args) {
int[] nums={4,5,1,6,2,7,3,8};
ArrayList exchange = GetLeastNumbers_Solution(nums,4);
for (Object o : exchange) {
System.out.println(o);
}
}
}